Một dãy gồm n số nguyên không âm a_1, _a_2,…, _an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n­-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-_1-_k) dấu trừ vào (n­-1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên không âm a_1, _a_2,…, _an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-_1-_k) dấu trừ vào (n­-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương n, k (k < n);
• Dòng thứ hai chứa n số nguyên không âm a_1, _a_2,…, _an (an ≤ 10^6)

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

Input
5 2
28 9 5 1 69

Output
100

Ghi chú:

• Có 50% số test ứng với 50% số điểm có n ≤ 10^5 và k = 1;
• Có 50% số test còn lại ứng với 50% số điểm có n ≤ 10^5;