3917: 张老师的羊腿橱柜
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
张老师为了能够更好的卖羊腿，听了黄老师的建议——在店门口摆上展示柜来吸引顾客
于是张老师买了一个有 $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$
现在张老师想知道，吸引力最大可以是多少？
于是张老师买了一个有 $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$
现在张老师想知道，吸引力最大可以是多少？
输入
输入第一行包含两个整数 $n,m$，含义如题
输入第二行包含 $n$ 个整数 $a_i$，分别表示每种羊腿单独放入展示柜时的吸引力
输入第二行包含 $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$
对于 $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$
输出
输出一行包含一个整数，表示最大吸引力
样例输入 复制
5 3
1 2 5 4 3样例输出 复制
6提示
样例解释1
选 $1,5,3$ 组成最大吸引力 $|1-5|+|5-3|=6$
样例解释2
选 $8,-2,5$ 组成最大吸引力 $|8-(-2)|+|(-2)-5|=17$
选 $1,5,3$ 组成最大吸引力 $|1-5|+|5-3|=6$
选 $8,-2,5$ 组成最大吸引力 $|8-(-2)|+|(-2)-5|=17$