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.

Dữ liệu vào:

• 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 (ai ≤ 10^6 ~ với mọi ~ 1≤ i ≤ n) ~.

Kết quả:

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

Ví dụ:

Input

5 2
28 9 5 1 69 

Output

100 

Ràng buộc:

• 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 ~;