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}\ (a_{i}\ \leq \ 10^{6}\) với mọi \(1 \leq \ i\ \leq \ n)\).

Kết quả:

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

Ví dụ:

Ghi chú:

• Có 50% số test ứng với 50% số điểm có \(n \leq \ 10^{5}\) và \(k\ = \ 1\);

• Có 50% số test còn lại ứng với 50% số điểm có \(n\ \leq \ 10^{5}\);