你正在处理一个包含 $n$ 个非负整数的序列。在这个游戏中，你需要将该序列分割成 $k+1$ 个非空部分。为了得到 $k+1$ 个部分，你需要重复执行以下步骤 $k$ 次：
- 选择任意一个包含多于一个元素的部分（初始时你只有一个部分，即整个序列）。
- 在任意两个元素之间将其分割，得到两个新的非空部分。
每次执行这些步骤后，你获得的得分等于这两个新部分元素之和的乘积。你希望最大化你获得的得分总和。
输入格式
第一行包含两个整数 $n$ 和 $k$ ($k + 1 \le n$)。第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^4$)，即该序列。
输出格式
第一行输出你能获得的最大得分总和。第二行输出 $k$ 个介于 $1$ 和 $n - 1$ 之间的整数，表示为了获得最大得分总和，你需要在哪几个位置之后对序列进行分割。如果存在多种获得最大得分的方法，输出其中任意一种即可。
样例
样例输入 1
7 3 4 1 3 4 0 2 3
样例输出 1
108 1 3 5
说明
在第一个样例中，你可以通过以下方式获得 108 分：
- 初始时，你拥有整个序列 $(4, 1, 3, 4, 0, 2, 3)$ 作为一部分。你在第 1 个元素之后分割序列，获得 $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ 分。
- 现在你有两个部分 $(4)$ 和 $(1, 3, 4, 0, 2, 3)$。你在第 3 个元素之后分割序列，获得 $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ 分。
- 现在你有三个部分 $(4)$、$(1, 3)$ 和 $(4, 0, 2, 3)$。你在第 5 个元素之后分割序列，获得 $(4 + 0) \times (2 + 3) = 20$ 分。
因此，经过上述步骤后，你得到了四个部分 $(4)$、$(1, 3)$、$(4, 0)$、$(2, 3)$，总得分为 $52 + 36 + 20 = 108$ 分。
子任务
你的程序将在 6 组输入实例上进行测试，具体如下：
- 子任务 1（11 分）：$1 \le k < n \le 10$。
- 子任务 2（11 分）：$1 \le k < n \le 50$。
- 子任务 3（11 分）：$1 \le k < n \le 200$。
- 子任务 4（17 分）：$2 \le n \le 1000$，$1 \le k \le \min(n - 1, 200)$。
- 子任务 5（21 分）：$2 \le n \le 10000$，$1 \le k \le \min(n - 1, 200)$。
- 子任务 6（29 分）：$2 \le n \le 100000$，$1 \le k \le \min(n - 1, 200)$。