Trò chơi với các hộp bi

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\le i\le n$) có $a_i$ ($0\le a_i\le {10}^9$) viên bi. Mỗi lượt, người chơi được 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 một 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 rỗng nhất.

Như vậy, mỗi lượt chọn một đoạn khác rỗng gồm các hộp liên tiếp mà tại thời điểm đó hộp nào trong đoạn cũng còn ít nhất một viên bi. Các hộp rỗng ngay từ đầu cũng được tính vào số hộp rỗng.

Yêu cầu: Cho $n,r$ và số lượng bi trong mỗi hộp, hãy tìm số lượng hộp 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.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n,r$;
• Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên là số lượng hộp rỗng nhiều nhất đạt được.

Ràng buộc

• $1\le n\le 2000$; $1\le r\le {10}^9$.
• $0\le a_i\le {10}^9$.

Subtasks

Điểm được tính theo từng test.

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

Ví dụ