Một ngày đẹp trời nọ có một siêu nhân chính là p2o2HuaGiaBao. Cậu ấy thấy dân tộc HGBCpp_ bị các tên ác nhân bao vây để làm chuyện xấu nên anh ta đã chuẩn bị ra tay. Các tên ác nhân đều là đàn em của Phụng Tỷ thuộc tập đoàn Người Thượng Vì Công Lý (MSFJ). Vì anh ta thấy hành vi này quá xấu nên quyết định ra tay. Nhưng vì nhân lực của họ quá mạnh nên phải tên chiến thuật hợp lí mà cậu ta tính bằng tay không nổi nên mới code. Tuy nhiên, máy tính và các thiết bị điện tử bị hỏng nên đành nhờ các bạn hỗ trợ siêu nhân p2o2HuaGiaBao tính toán nhé! Chiến lược như sau:
Siêu nhân p2o2HuaGiaBao phải đối đầu với \(n\) tên ác nhân, những tên ác nhân này được đánh số từ \(1\) đến \(n\), mỗi tên thứ \(i\) có sức mạnh là \(a_{i}\). Siêu nhân muốn nâng cấp sức mạnh bằng cách chia \(n\) tên ác nhân thành \(k\) nhóm liên tiếp \([l_i, r_i]\) thỏa mãn các điều kiện phân chia (như \(l_1=1, r_k=n\)). Sức mạnh tăng thêm được tính bằng công thức tổng \(\sum_{i=1}^{k} f(l_i, r_i)\), trong đó \(f(x, y) = a_x - a_{x+1} + a_{x+2} - \dots \pm a_y\).Nhiệm vụ là tìm cách chia để tổng sức mạnh này là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\) (\(1\le k\le n\le 2\times 10^{5}\))
• Dòng thư hai gồm \(n\) số nguyên dương \(a_1,a_2,a_3,...,a_n\) (\(a_i\le 10^{9}\), \(1\le i\le n\))

Output

• Gồm một dòng chứa kết quả bài toán – sức mạnh tăng thêm lớn nhất của siêu nhân.

Example

5 5
1 2 3 4 5

15

10 4
4 5 8 29 5 4524 355 853 2539 2435

10027