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 < 10^5)~;
• Dòng thứ hai chứa N số nguyên không âm ~(A_N \le 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