BIỂU THỨC (4,0 điểm):

          Mai và Lan đố nhau bài toán cho một dãy gồm n số nguyên không âm a₁,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ó (n-1) khoảng trắng. Người ta muốn đặt k dấu trừ và (n-1-k) dấu cộng vào (n-1) khoảng trắng đó để nhận được biểu thức có giá trị lớn nhất.

Ví dụ: với dãy gồm 5 số nguyên 20 15 25 5 3 với k =2 thì cách đặt 20+15+25-5-3 là biểu thức có giá trị lớn nhất.

- Yêu cầu: một dãy gồm n số nguyên không âm a₁,a_2,..a_n và số nguyên dương k, hãy tìm cách đặt k dấu trừ và (n-1-k) dấu cộng 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: Cho từ file BAI3.INP gồm:

+ Dòng 1 chứa hai số nguyên n, k (0<k<n <= 10⁶)

+ Dòng 2 chứa n số nguyên không âm a₁,a_2,..a_n (0  a_i <=10⁶, i=1 .. n)

- Kết quả ra: Ghi ra file BAI3.OUT gồm một số nguyên là giá trị của biểu thức đạt được.

- Ví dụ:

- Ràng buộc:

+ 60% số test ứng với n <=10³    

+ 40% số test còn lại không có ràng buộc gì thêm.