Bài 3. (4 điểm) Biểu thức

Cho dãy số A gồm N số nguyên không âm a₁, a₂,..., a_N được viết thành một hàng ngang, giữa hai số liên tiếp nhau có một khoảng trắng, như vậy có tất cả N-1 khoảng trắng.

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 khi viết dãy số A thành một hàng ngang như đã nói trên để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ với dãy số A gồm 5 số nguyên 28, 9, 5, 1, 69 và K = 2 thì cách đặt 2 dấu cộng, 2 dấu trừ tạo thành biểu thức 28+9-5-1+69 có giá trị lớn nhất.

Dữ liệu vào từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng đầu tiên ghi hai số nguyên dương N, K (K < N);
• Dòng thứ hai ghi N số nguyên không âm a₁, a₂,..., a_N (a_N ≤ 10⁶);
• Các số trên mỗi dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra ghi vào tệp văn bản BAI3.OUT một số nguyên là giá trị của biểu thức tìm được theo yêu cầu.