Biểu thức (Tham lam, 2*)

Một dãy gồm \(n\) số nguyên \(a_{1}, 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ó 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 \(a_{1}, a_{2},..., a_{n}\) 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 \(a_{1}, a_{2},..., a_{n}\) \((|a_{i}| ≤ 10^6)\)

Output

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

Example

5 2
28 9 5 1 69

100

Scoring

\(60\%\) số test có \(n \leq 20\).

\(40\%\) số test còn lại có \(n \leq 10^5\).