#CS1161. 棍子分割

棍子分割

题目背景

翻译自 CSES-1161 题。

题目描述

你有一根长度为 x 的棍子，你需要将它分割成 n 根长度已知的棍子，且这些棍子的总长度为 x。

在每次操作中，你可以选择一根棍子将其分割成两根。每次操作的成本为原始棍子的长度。

问题是：你需要计算分割这些棍子所需的最小成本。

输入格式

第一行包含两个整数 x 和 n，表示棍子的长度和需要分割成的棍子数量。

第二行包含 n 个整数 d1,d2,…,dnd_1, d_2, \dots, d_nd1​,d2​,…,dn​，表示每根棍子的长度。

输出格式

输出一个整数，表示分割的最小成本。

样例

8 3
2 3 3

13

样例1解释 你首先将长度为 8 的棍子分割成长度为 3 和 5 的两根棍子（操作成本为 8）。然后，将长度为 5 的棍子再分割成长度为 2 和 3 的两根棍子（操作成本为 5）。最终总成本为 8+5=138 + 5 = 138+5=13。

说明/提示

$1 \leq x \leq 10^9$

$1 \leq n \leq 2 \times 10^5$

∑di=x\sum d_i = x∑di​=x，即这些棍子的总长度等于原始棍子的长度。