Biểu thức

Một dãy gồm $n$ số nguyên không âm $a_1,a_2,\dots ,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. Thứ tự các số được giữ nguyên; trước $a_1$ không có dấu nên $a_1$ luôn được cộng vào biểu thức.

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,\dots ,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.

Dữ liệu vào

• 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,\dots ,a_n$ ($a_i\le {10}^6$).

Dữ liệu ra

In ra một số nguyên là giá trị lớn nhất của biểu thức đặt được (giá trị này có thể âm).

Ràng buộc

• $2\le n\le {10}^5$, $1\le k<n$.
• $0\le a_i\le {10}^6$.

Subtasks

• Có $50\%$ số test ứng với $50\%$ số điểm có $n\le {10}^5$ và $k=1$.
• Có $50\%$ số test còn lại ứng với $50\%$ số điểm có $n\le {10}^5$.

Ví dụ