Cho một dãy số gồm \(n\) số nguyên không âm \(a_{1},\ a_{2},\ \ldots,\ a_{n}\), 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.

Yêu cầu: Tìm giá trị lớn nhất của biểu thức thỏa yêu cầu trên.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương \(n,\ k\ (k\ < \ n\ \leq \ 10^{5})\);

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

Các số trên cùng một dòng cách nhau ít nhất một dấu cách.

Kết quả: Một số nguyên cho biết giá trị của biểu thức lớn nhất.

Ví dụ:

Giải thích: Dãy số 28, 9, 5, 1, 69 với K = 2 thì cách đặt 28+9-5-1+69=100 là biểu thức có giá trị lớn nhất.