An đang chuẩn bị một bữa tiệc cho bạn bè của mình. Bữa tiệc bao gồm \(n\) đĩa thức ăn được xếp thành một hàng, đĩa thứ \(i\) tính từ đầu bên trái cho \(a_i\) điểm hài lòng nếu được ăn. Một số đĩa thức ăn không ngon, nên điểm \(a_i\) có thể bằng 0 hoặc bằng số âm.

Có \(k\) người tham gia bữa tiệc và mỗi người sẽ được giao một đoạn đĩa liên tiếp để ăn, đoạn này có thể trống. Các đoạn của hai người không được giao nhau, vì thức ăn không thể ăn hai lần. An muốn phân bổ các đĩa thức ăn cho bạn bè của mình sao cho tổng điểm hài lòng của tất cả các đĩa thức ăn được phân bổ là tối đa.

Input

-Dòng đầu tiên chứa hai số nguyên \(n\) và \(k (1≤k≤n≤3×10^5 ). \)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^9 ).\)

Output

• Ghi một số nguyên là tổng điểm hài lòng của cách phân bổ tối ưu.

Sample Input

6 1
1 -2 3 -1 5 -6

Sample Output

7

Giải thích:

• cách phân bổ tối ưu cho một người là đoạn [3,-1,5].

Ràng buộc:

• Subtask 1: \(a_i≥0;\)

• Subtask 2: có đúng một số \(a_i<0;\)

• Subtask 3: \( k=1;\)

• Subtask 4: \( 1≤k≤n≤80;\)

• Subtask 5: \(1≤k≤n≤300;\)

• Subtask 6: \( 1≤k≤n≤2000;\)