Một dãy gồm \(n\) số nguyên không âm \(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.

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\) \((k \leq n \leq 10^{5})\);
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1}, a_{2},..., a_{n}\) \((1 \leq i \leq n; a_{i} \leq 10^{6})\).

Output

• Gồm 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

5 1
10 20 15 5 1

9