给定一个长度为 n 和数字 k 的数组。让我们从初始数组中选择 k 个不重叠的非空子数组。令 si 为从左到右顺序的第 i 个子数组的和。计算以下表达式的最大值:
|s1 - s2| + |s2 - s3| + ... + |sk - 1 - sk|
这里的子数组是数组的连续部分。
输入
输入的第一行包含两个整数 n 和 k。第二行包含 n 个整数——数组的元素。元素的绝对值不超过104。
该问题由两个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。
- 在子问题 E1(9 点)中,约束 2 ≤ n ≤ 400、2 ≤ k ≤ min(n, 50) 将成立。
- 在子问题 E2(12 点)中,约束 2 ≤ n ≤ 30000、2 ≤ k ≤ min(n, 200) 将成立。
输出
输出一个整数——最大可能值。
示例
输入 #1
5 3 5 2 4 3 1
输出 #1
12
输入 #2
4 2 7 4 3 7
输出 #2
8
注意
考虑第一个样本测试。如果第一个子数组仅包含第一个元素,第二个子数组跨越接下来的三个元素,最后一个子数组仅包含最后一个元素,则获得最佳解决方案。这些子数组的和分别为 5、9 和 1。
考虑第二个样本测试。在最优解中,第一个子数组由前两个元素组成,第二个子数组仅由第三个元素组成。请注意,最后一个元素不属于此解决方案中的任何子数组。