题目描述

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

于是徐老师买了一个有 $m$ 个格子的展示柜

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

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

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

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

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

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

现在徐老师想知道，吸引力最大可以是多少？

输入格式

本题采用文件读写。

• 读入文件名：cabinet.in
• 写出文件名：cabinet.out

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

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

输出格式

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

样例

5 3
1 2 5 4 3

6

样例 1 说明

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

5 3
3 6 8 -2 5

17

样例 2 说明

选 $8,-2,5$ 组成最大吸引力 $|8-(-2)|+|(-2)-5|=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 <= n$