Sau cuộc phiêu lưu cùng nhau, Dế Mèn và Dế Trũi lên kế hoạch trở về quê nhà. Hành trình trở về quê của hai bạn sẽ đi qua \(n\) thành phố, các thành phố lần lượt đi qua từ \(1\) đến \(n\). Giá bán một xe cỏ tại thành phố \(i\) là \(a_i\). Nếu mua một xe cỏ ở thành phố \(i\) mang đến thành phố \(j\) để bán thì thu được lợi nhuận là \(a_j-a_i\).

Vì giao thông không thuận lợi nên mỗi lần chỉ mang được tối đa một xe cỏ. Để đảm bảo thời gian di chuyển nên số lần mua và bán một xe cỏ không vượt quá \(k\) lần.

Yêu cầu: Tính tổng lợi nhuận tối đa mà hai bạn có thể thu được trên hành trình trở về quê nhà.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,k (k≤n≤2*10^5 ).\)

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n.\)

Output

• Ghi tổng lợi nhuận lớn nhất thu được.

Ràng buộc:

• Subtask 1: 20% test với \(k=1\).

• Subtask 2: 30% số test với \(k=2\).

• Subtask 3: 30% test với \(3≤k≤100\).

• Subtask 4: 20% số test với \(k≤n≤2*10^5.\)

Sample Input

5 1
4 1 3 5 6

Sample Output

5

Sample Input

5 2
1 4 2 5 6

Sample Output

7