You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Z为了能够更好的卖羊腿，听了黄老师的建议——在店门口摆上展示柜来吸引顾客

于是小Z买了一个有 $m$ 个格子的展示柜

在店内，一共有 $n$ 种不同种类的羊腿可供挑选，而小Z决定从中选出 $m$ 种羊腿各放一只到展示柜里

为了被展示柜里的羊腿吸引的顾客进店后能够快速找到自己想要的羊腿，小Z决定不能打乱这些羊腿原有的相对顺序，比如有五种羊腿依次排列为 $A,B,C,D,E$，那么从中选出三种羊腿放入展示柜的方案只能是 $(A,B,C),(A,C,D),(A,C,E) \dots$ 不能是 $(A,C,B),(A,D,C)$ 等

但是羊腿们摆放在一起会产生不同的化学效应，导致看起来更加美观或者不那么美观

为了方便进行计算，小Z统计了这 $n$ 种羊腿单独放入展示柜时的吸引力 $a_i$

而最终放入展示柜的 $m$ 种羊腿能够产生的总吸引力是 相邻两种羊腿的吸引力之差的和

例如有 $5$ 种羊腿，吸引力分别为 $1,2,5,4,3$，选出三种羊腿 $(1,5,3)$，那么总吸引力是 $|1-5|+|5-3|=6$

现在小Z想知道，吸引力最大可以是多少？

输入格式

输入第一行包含两个整数 $n,m$，含义如题

输入第二行包含 $n$ 个整数 $a_i$，分别表示每种羊腿单独放入展示柜时的吸引力

输出格式

输出一行包含一个整数，表示最大吸引力

数据范围

对于 $20\%$ 的数据，满足 $n \le 5$，$-100 \le a_i \le 100$。

对于 $50\%$ 的数据，满足 $n \le 20$，$-10^6 \le a_i \le 10^6$。

对于 $100\%$ 的数据，满足 $1\le n \le 300$，$-10^9 \le a_i \le 10^9$。

特别的，保证所有 $m <= n$

样例输入1

5 3
1 2 5 4 3

样例输出1

6

样例解释1

选 $1,5,3$ 组成最大吸引力 $|1-5|+|5-3|=6$

样例输入2

5 3
3 6 8 -2 5

样例输出2

17

样例解释2

选 $8,-2,5$ 组成最大吸引力 $|8-(-2)|+|(-2)-5|=17$