星光咖啡馆即将推出新一季的甜点菜单。

为了准备这份菜单，四季夏目连续制作了许多甜点试作品，并为每一份记录了对应的风味值。只是，甜点的数量实在太多，若只是按照制作顺序将它们全部放上菜单，难免显得杂乱，也无法充分展现每一份甜点的特点。

而距离菜单的更新已经没有多少时间了。

看着桌上排列整齐的试作品，夏目决定重新整理整份菜单，使这些甜点能够获得尽可能高的总评价。

桌上的甜点试作品按照制作顺序排列，共有 n 份。第 i 份甜点的风味值为非负整数 a_i。

夏目准备将这 n 份甜点按照原有顺序划分成恰好 k 组。每一组都必须由若干份连续的甜点组成，并且每份甜点恰好属于其中一组。

对于一组包含第 l 份至第 r 份甜点的组合，夏目会从中选择一份甜点作为这一组的主打甜点。若选择第 p 份甜点作为主打甜点（l\le p\le r），则这一组获得的评价为：

即对于一个确定的 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] 的最高评价为：

也就是对于所有的下标满足 l\le p \le r 的 w_p 中的最大值。

设最终划分出的 k 组甜点对应的区间依次为：

[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]

这些区间需要满足：

整份菜单的总评价为：

\sum_{i=1}^{k}f(l_i,r_i)

也就是将所有的 f(l_i,r_i) \quad (1\le i \le k) 加起来。

请你求出整份菜单能够获得的最大总评价。

第一行两个正整数 n, k 分别表示序列的长度和划分的段数。

第二行 n 个非负整数 a_1, a_2, ... , a_n 表示非负整数序列 a。

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

对于所有数据保证，0 \le a_i \le 10^9，1 \le k \le n。

洛谷月赛