序列分组

题目描述

Y 同学拿到了一份包含 $N$ 个正整数的序列 $A = \{a_1, a_2, \ldots, a_N\}$。

为了分析这个序列的特征，Y 同学决定将其拆分成 $K$ 个连续的子段（组）。也就是说，他需要找到 $K-1$ 个分割点，将序列切开，使得每个元素都恰好属于某一个子段，且子段内部的元素在原序列中是连续的。

对于每一个划分出的子段，Y 同学定义其得分为：该子段内元素的最大值与最小值的差。 即对于子段 $S = \{x_1, x_2, \ldots, x_m\}$，其得分为 $\max(S) - \min(S)$。

Y 同学的目标是最大化所有 $K$ 个子段的得分之和。请你帮助他计算出在所有合法的划分方案中，能够获得的最大总得分。

输入格式

第一行包含两个正整数 $N$ 和 $K$，分别表示序列的长度和需要划分的组数。 第二行包含 $N$ 个正整数 $a_1, a_2, \ldots, a_N$，表示给定的序列。

输出格式

输出一行一个整数，表示最大总得分。

样例

样例输入 #1

5 2
1 3 4 1 2

样例输出 #1

5

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le K \le N \le 100$，$1 \le a_i \le 10^9$。