Cho một dãy gồm n số nguyên không âm a₁, a₂, …, aₙ được viết thành một hàng ngang, giữa hai số liên tiếp có tất cả n-1 khoảng trắng. Người ta muốn đặt vào đó đúng k dấu cộng (+) và đúng n-1-k dấu trừ (-) để nhận được một biểu thức có giá trị lớn nhất.

Hãy tìm giá trị lớn nhất có thể đạt được.

Input: Dòng 1: hai số nguyên n và k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ n-1); Dòng 2: n số nguyên không âm a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10⁹).

Output: Một số nguyên duy nhất: giá trị lớn nhất có thể đạt được

Example Input

5 2
28 9 5 1 69

Output

100

Giới hạn Subtask 1 (50%): n ≤ 20. Subtask 2 (50%): n ≤ 10^5.