### 问题描述 辉神正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中他需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，他需要重复下面的操作 $k$ 次： 1. 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）。 2. 选择两个相邻元素把这个块从中间分开，得到两个非空的块。 每次操作后他将获得那两个新产生的块的元素和的乘积的分数，他想要最大化最后的总得分。 ### 输入格式 第一行包含两个整数 $n$ 和 $k$。 第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示前文所述的序列。 ### 输出格式 输出一个整数，表示他能获得的最大总得分。 ### 样例输入 ``` 7 3 4 1 3 4 0 2 3 ``` ### 样例输出 ``` 108 ``` ### 评测数据规模 $2 \leq n \leq 10^5$，$1 \leq k \leq \min \\{n - 1, 200\\}$，$0 \leq a_i \leq 10^4$。