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

1. 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
2. 选择两个相邻元素把这个块从中间分开，得到两个非空的块。

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

输入格式

第一行包含两个整数 $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$ 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 $i$ 个整数 $s_i$ 表示第 $i$ 次操作将在 $s_i$ 和 $s_{i+1}$ 之间把块分开。

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

样例一

input

7 3
4 1 3 4 0 2 3

output

108
1 3 5

explanation

你可以通过下面这些操作获得 $108$ 分：

1. 初始时你有一块 $(4,1,3,4,0,2,3)$。在第 $1$ 个元素后面分开，获得 $4\times (1+3+4+0+2+3)=52$ 分。
2. 你现在有两块 $(4),(1,3,4,0,2,3)$。在第 $3$ 个元素后面分开，获得 $(1+3)\times (4+0+2+3)=36$ 分。
3. 你现在有三块 $(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$ 分。

限制与约定

第一个子任务共 11 分，满足 $1\le k<n\le 10$。

第二个子任务共 11 分，满足 $1\le k<n\le 50$。

第三个子任务共 11 分，满足 $1\le k<n\le 200$。

第四个子任务共 17 分，满足 $2\le n\le 1000,1\le k\le min\{n-1,200\}$。

第五个子任务共 21 分，满足 $2\le n\le 10000,1\le k\le min\{n-1,200\}$。

第六个子任务共 29 分，满足 $2\le n\le 100000,1\le k\le min\{n-1,200\}$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载