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.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có n ≤ \(10^5\) và k = 1;
• Có 50% số test còn lại ứng với 50% số điểm có n ≤ \(10^5\), k > 1.

Dữ liệu vào:

từ file văn bản EXPRESS.INP:
- 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] ≤ \(10^6\) với mọi 1 ≤ i ≤ n).

Dữ liệu ra:

Đưa ra file văn bản EXPRESS.OUT một số nguyên là giá trị của biểu thức đặt được.

5 2
28 9 5 1 69

100