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 \leq 10^{6})~

Output

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

Giới hạn

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

Sample Input

5 2
28 9 5 1 69

Sample Output

100