题目背景

翻译自 CSES-1161 题。

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

8 3
2 3 3

13

提示

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

数据范围

• $1 \le x \le 10^9$
• $1 \le n \le 2 \times 10^5$
• $\sum d_i = x$，即这些棍子的总长度等于原始棍子的长度