Description:


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

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

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

Input:


第一行包含两个整数 \(n\)\(k\) 。保证 \(k+1\le n\)

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

Output:


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

UOJ还有方案:

第二行输出 \(k\) 个介于 \(1\)\(n-1\) 之间的整数,表示为了使得总得分最大,你每次操作中分开两个块的位置。第 \(i\) 个整数 \(s_i\) 表示第 \(i\) 次操作将在 \(s_i\)\(s_i+1\) 之间把块分开。

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

Sample Input:


Sample Output:


题解:


可以发现一个明显的DP:

然后用斜率搞一搞(因为有斜率为正无穷的情况,所以我就用叉积来写的)