题目背景

翻译自 CSES-1161 题。

题目描述

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

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

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

输入格式

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

第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$，表示每根棍子的长度。

输出格式

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

样例

8 3
2 3 3

13

样例1解释

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

说明/提示

$1 \leq x \leq 10^9$；

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

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