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 khả năng xây dựng 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.

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.

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 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.

Sample Input 1

6 2
0 2 1 2 2 3

Sample Output 1

4

Giải thích:

• Lượt 1: Chọn đoạn từ hộp thứ 2 đến hộp thứ 5, trạng thái các hộp bi: 0 1 0 1 1 3.
• Lượt 2: Chọn đoạn từ hộp thứ 4 đến hộp thứ 5, trạng thái các hộp bi: 0 1 0 0 0 3. Như vậy, có 4 hộp rỗng.

Subtasks

• 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~.