题目内容

给定一个数组$a_i$ , 可以将他们分成$k$个连续子数组(不允许打乱)。使得每组的极差的和最大。求这个最大值。

限定条件:

1.每一组至少一个数

2.极差:最大值减最小值

输入描述

第一行输入两个整数$n , k(1 \leq k \leq n \leq 200)$ 。

第二行输入$n$个整数$a_1,a_2,...,a_n(1 \leq a_i \leq 1e9)$

输出描述

输出极差最大值。

样例1

输入

5 2
7 6 2 4 8

输出

9

样例2

输入

4 1
7 6 7 8

输出

2

样例3

输入

4 2
8 8 2 2

输出

6