Cho mảng \(A\) gồm \(n\) phần tử nguyên. Bạn có thể thực hiện thao tác sau không quá \(k\) lần:

• Chọn 2 chỉ số \(l, r\) sao cho \(1 \le l \le r \le n\), gán \(0\) cho tất cả các phần tử \(A_l, A_{l + 1},...,A_r\).

Tìm tổng lớn nhất có thể của \(A\) sau khi thực hiện một số thao tác.

Input

• Dòng đầu tiên gồm 2 số nguyên \(n, k\).
• Dòng tiếp theo gồm \(n\) số nguyên \(A_i\).

Output

• In ra tổng lớn nhất có thể của mảng \(A\).

Điều kiện

• \(1 \le n, k \le 5000\).
• \(|A_i| \le 10^9\).

Ví dụ

Input:

4 1
1 -3 1 -10

Output:

1