Link bài gốc : http://vnoi.info/problems/show/DHEXP/

Đề bài :

Một dãy gồm n số nguyên không âm a_1, _a_2,…, an_ đượ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 đó để 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à k = 2 thì cách đặt 28+9-5-1+69 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 _a_1, _a_2,…, an_ và số nguyên dương k, 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 để nhận được một 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 (k < n)
• Dòng thứ hai chứa n số nguyên không âm a_1, a_2,…, aN _(ai _≤ 10^6)

Output

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

Ví dụ

Input

5 2
28 9 5 1 69

Output

100

Solution

Tham Khảo Tại : http://dataurbia.com/15oD

Code

Tham Khảo Tại : http://dataurbia.com/15m3