Để tạo hiệu ứng kinh doanh tốt hơn, nông trại X thực hiện chiến lược kinh doanh như sau: Bày ~N~ giỏ trái cây thành một hàng trên kệ bán dọc đường vào nông trại, các giỏ trái cây được đánh số từ ~1~ đến ~N~. Độ ngon của giỏ trái cây thứ ~i~ là ~A_i~.

• Mỗi khách chỉ được mua những giỏ trái cây liên tiếp.
• Mỗi giỏ trái cây chỉ bán cho tối đa một khách (có thể không bán cho ai).
• Độ hài lòng của một khách hàng sau khi mua trái cây được tính bằng tổng độ ngon của các giỏ trái cây mà khách hàng đó nhận được (nếu không nhận được giỏ trái cây nào thì độ hài lòng bằng ~0~).

Có ~K~ khách hàng đến mua trái cây, người chủ nông trại muốn bán các giỏ trái cây cho khách hàng sao cho tổng độ hài lòng của ~K~ khách hàng là lớn nhất.

Yêu cầu: Hãy tính tổng độ hài lòng lớn nhất của ~K~ khách hàng.

Input

• Dòng đầu ghi hai số nguyên dương ~N, K~ (~K \le N \le 3 \cdot 10^5~).
• Dòng thứ hai ghi lần lượt ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~|A_i| \le 10^9~). Các số ghi trên một dòng cách nhau một dấu cách.

Output

Ghi ra một số nguyên là tổng độ hài lòng lớn nhất của ~K~ khách hàng.

Scoring

Sample Input 1

6 2
-1 4 6 -1 8 9

Sample Output 1

27

Notes

Khách hàng ~1~ nhận giỏ thứ ~\{2, 3\}~, khách hàng ~2~ nhận giỏ thứ ~\{5, 6\}~ có tổng độ ngon lớn nhất là ~(4+6) + (8+9) = 27~.