(ptit016d.*)

Một dãy gồm \(n\) số nguyên không âm \(a_{1},a_{2},\ldots,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 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},\ldots,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\ \left( k < n \leq 10^{5} \right)\)

+ Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1},a_{2},\ldots,a_{n}\) \((0 < a_{i} \leq 10^{6})\)

Kết quả:

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

Ví dụ: