题目描述

$Sam$ 为了能够更好的卖羊腿，听了 $Paul$ 的建议——在店门口摆上展示柜来吸引顾客。

于是 $Sam$ 买了一个有 $m$ 个格子的展示柜。

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5 3
1 2 5 4 3

输出 #1

6

输入输出样例 #2

输入 #2

5 3
3 6 8 -2 5

输出 #2

17

说明/提示

数据范围

对于 $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\le n$。

样例解释1

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

样例解释2

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