Một dãy gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ đượ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, ..., a_n~ 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, ..., a_n~ (~a_i \le 10^6~).

Output

• Đưa ra một số nguyên là giá trị của biểu thức đặt được.

Sample Input 1

5 2
28 9 5 1 69

Sample Output 1

100

Subtasks

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