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~
• Dòng thứ hai chứa n số nguyên không âm ~a_1~,~a_2~,...,~a_n~

Giới hạn:

• ~k < n~ ≤ ~10^5~
• ~a_i~ <= ~10^6~

Kết quả:

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

Ví dụ:

Input 1:

5 2
28 9 5 1 69

Output 1:

100