Bài toán dưới đây có rất nhiều cách tiếp cận, bài toán rất phù hợp để giảng dạy và kiểm tra về nội dung các chiến lược phân tích thiết kế thuật toán, bài toán như sau: Có n hộp bi xếp thành một hàng, hộp thứ ~i(1≤i≤n)~có ~A_i (0≤A_i ≤10^9)~ viên bi. Mỗi lượt, người chơi được quyền chọn một đoạn gồm các hộp bi liên tiếp vẫn còn bi và lấy ra từ mỗi hộp 1 viên bi. Người chơi được thực hiện không quá r lượt và mong muốn làm cho nhiều hộp bi rỗng nhất có thể.

Dữ liệu:

Dòng đầu chứa 2 số nguyên dương n, r.
Dòng thứ hai chứa n số nguyên dương không âm A1, A2, ... , An.

Kết quả:

Ghi ra một số nguyên là số lượng hộp bi rỗng nhiều nhất đạt được nếu người chơi biết chiến lược chơi tối ưu.

Ràng buộc:

● Có 20% số lượng test ứng với 20% số điểm thỏa mãn : ~n≤10;r=1~;
● Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn: ~n≤10;r≤5~;
● Có 30% số lượng test khác ứng với 30% số điểm thỏa mãn: ~n≤200; r≤200~;
● Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn: ~n≤200;r≤10^9~;
● Có 10% số lượng test còn lại ứng với 10% số điểm thỏa mãn: ~n≤2000; r≤10^9~;

Sample Input 1:

6 2
0 2 1 2 2 3

Sample Output 1:

4

Sample Input 2:

13 4
0 3 3 3 3 0 0 2 2 0 1 2 3

Sample Output 2:

9