P17078 夏日甜点

星光咖啡馆即将推出新一季的甜点菜单。 为了准备这份菜单，四季夏目连续制作了许多甜点试作品，并为每一份记录了对应的风味值。只是，甜点的数量实在太多，若只是按照制作顺序将它们全部放上菜单，难免显得杂乱，也无法充分展现每一份甜点的特点。 而距离菜单的更新已经没有多少时间了。 看着桌上排列整齐的试作品，夏目决定重新整理整份菜单，使这些甜点能够获得尽可能高的总评价。

桌上的甜点试作品按照制作顺序排列，共有 $n$ 份。第 $i$ 份甜点的风味值为非负整数 $a_i$。 夏目准备将这 $n$ 份甜点按照原有顺序划分成恰好 $k$ 组。每一组都必须由若干份连续的甜点组成，并且每份甜点恰好属于其中一组。 对于一组包含第 $l$ 份至第 $r$ 份甜点的组合，夏目会从中选择一份甜点作为这一组的主打甜点。若选择第 $p$ 份甜点作为主打甜点（$l\le p\le r$），则这一组获得的评价为： $$ (r-l+1)a_p-\sum_{i=l}^{r}|a_i-a_p| $$ 即对于一个确定的 $p$，评价就是 $(r-l+1)\times a_p$ 减去所有满足 $l\le i \le r$ 的 $a_i$ 与 $a_p$ 相减的绝对值之和（即满足 $l\le i \le r$ 的 $|a_i-a_p|$ 之和）。我们记录这个值为 $w_p$。 夏目会选择使评价最高的甜点作为这一组的主打甜点。因此，定义区间 $[l,r]$ 的最高评价为： $$ f(l,r)=\max_{l\le p\le r}\left((r-l+1)a_p-\sum_{i=l}^{r}|a_i-a_p|\right) $$ 也就是对于所有的下标满足 $l\le p \le r$ 的 $w_p$ 中的最大值。 设最终划分出的 $k$ 组甜点对应的区间依次为： $$ [l_1,r_1],[l_2,r_2],\dots,[l_k,r_k] $$ 这些区间需要满足： $$ l_1=1,\quad r_k=n,\quad r_i+1=l_{i+1}\quad(1\le i

第一行两个正整数 $n, k$ 分别表示序列的长度和划分的段数。 第二行 $n$ 个非负整数 $a_1, a_2, ... , a_n$ 表示非负整数序列 $a$。

输出一行仅一个数表示答案。

### 时空限制 时间限制：$1.0\,\text{s}$。 空间限制：$512\,\text{MiB}$。 ### 数据范围 **本题采用捆绑测试**。 ::cute-table{tuack} | Subtask | $n \le$ | 分值 | |:-:|:-:|:-:| | $1$ | $50$ | $20$ | | $2$ | $500$ | $20$ | | $3$ | $5 \times 10^3$ | $20$ | | $4$ | $10^5$ | $40$ | 对于所有数据保证，$0 \le a_i \le 10^9$，$1 \le k \le n$。 注：数据点 $1\sim4$ 分别是四个 Subtask 的 hack 数据。其余数据点中，数据点 $5\sim8$ 属于 Subtask $1$，数据点 $9\sim12$ 属于 Subtask $2$，数据点 $13\sim16$ 属于 Subtask $3$，数据点 $17\sim24$ 属于 Subtask $4$。 ### 特别鸣谢 Idea - Na1L0n9。