Thao tác xóa

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 hai chỉ số \(l, r\) sao cho \(1 \le l \le r \le n\) và gán \(0\) cho tất cả các phần tử \(A_l, A_{l+1}, \ldots, 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 (có thể thực hiện ít hơn \(k\) lần, kể cả không thực hiện lần nào).

Input

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le n, k \le 5000\)).

• Dòng tiếp theo gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(|A_i| \le 10^9\)).

Output

In ra một số nguyên duy nhất là tổng lớn nhất có thể của mảng \(A\) sau khi thực hiện các thao tác.

Example

Input:

4 1
1 -3 1 -10

Output:

1

Note

Với ví dụ trên, chọn \(l = 2, r = 4\) và gán \(0\) cho \(A_2, A_3, A_4\), mảng trở thành \([1, 0, 0, 0]\) với tổng bằng \(1\), đây là tổng lớn nhất có thể đạt được khi chỉ dùng tối đa \(1\) thao tác.