Mô tả và yêu cầu

Một dãy gồm 𝑛 số nguyên không âm 𝑎1, 𝑎2,… ,𝑎𝑛 đượ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ả 𝑛 − 1 khoảng trắng. Người ta muốn đặt
𝑘 dấu cộng và (𝑛 − 1 − 𝑘) dấu trừ vào (𝑛 − 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à 𝑘 = 2 thì cách đặt 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 𝑎1, 𝑎2, … ,𝑎𝑛 và số nguyên dương 𝑘, hãy
tìm cách đặt 𝑘 dấu cộng và (𝑛 − 1 − 𝑘) dấu trừ vào (𝑛 − 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 𝑛, 𝑘 (𝑘 < 𝑛 ≤ 105)
+ Dòng thứ hai chứa 𝑛 số nguyên không âm 𝑎1, 𝑎2, … ,𝑎𝑛 (0 < 𝑎𝑖 ≤ 106)

Dữ liệu ra

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

Ví dụ

Input                Output
                                  5 2                   100
                                  28 9 5 1 69