你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k + 1 个非空的块。为了得到 k + 1 块，你需要重复下面的操作 k 次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

第一行包含两个整数 n 和 k。保证 k + 1 \leq n。

第二行包含 n 个非负整数 a_1, a_2, \cdots, a_n (0 \leq a_i \leq 10^4)，表示前文所述的序列。

第一行输出你能获得的最大总得分。

第二行输出 k 个介于 1 到 n - 1 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 i 个整数 s_i 表示第 i 次操作将在$si和s{i+1}$之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

你可以通过下面这些操作获得 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 分。

2 \leq n \leq 100000, 1 \leq k \leq min(n - 1, 200)。保证最大得分不超过long long

APIO