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 ~

Kết quả

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

Ràng buộc

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

Ví dụ:

Input 1

5 2
28 9 5 1 69 

Output 1

100