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 \(b_{i}\). 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.

Input

• 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},…,a_{n}\).

Output

• Ghi ra file thiết bị ra chuẩn một số nguyên là 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.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\le 10, r=1\);
• Subtask \(2\) (\(30\%\) số điểm): \(n\le 10, r\le 5\);
• Subtask \(3\) (\(30\%\) số điểm): \(n\le 200, r\le 200\);
• Subtask \(4\) (\(20\%\) số điểm):\(n\le 200, r\le 10^9\);
• Subtask \(5\) (\(10\%\) số điểm): \(n\le 2000, r\le 10^9\).

Example

6 2
0 2 1 2 2 3

4