Một dãy 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 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 đó để đượ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 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₁, a₂, ..., a_n và số nguyên dương k 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 biểu thức có giá trị lớn nhất.

Input

- Dòng đầu chứa hai số nguyên dương n, k (0 < k < n ≤ 10⁶);
- Dòng thứ hai chứa n số nguyên không âm a₁, a₂, ..., a_n (0 < a_i ≤ 10⁶; với mọi số i = 1, 2, ..., n)

Output:

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

Ràng buộc:

- Có 50% số test ứng với 50% số điểm với n ≤ 10³;
- Có 50% số test còn lại ứng với 50% số điểm không có giới hạn gì thêm.

Ví dụ:

Input

5 2
28 9 5 1 69

Output

100