Hàng năm, vào mùa mận chín, cao nguyên Mộc Châu (Sơn La) lại rộn ràng tổ chức lễ hội hái mận. Tại một vườn mận nọ, có cây mận được trồng thành một hàng thẳng tắp, đánh số từ đến . Cây mận thứ có năng suất là kg quả.
Một nhóm học sinh trường nội trú tại Sơn La tham gia trải nghiệm hái mận. Các em được giao một chiếc gùi có sức chứa tối đa là kg. Để thuận tiện cho việc di chuyển, nhóm quyết định sẽ chỉ hái mận ở một dãy các cây liên tiếp nhau trên hàng.
Nhiệm vụ của bạn là giúp các bạn học sinh xác định xem có thể hái mận ở tối đa bao nhiêu cây liên tiếp sao cho tổng khối lượng mận thu hoạch được không vượt quá sức chứa của gùi.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và ().
Dòng thứ hai chứa số nguyên dương ().
Kết quả:
In ra một số nguyên duy nhất là số lượng cây mận tối đa trong đoạn liên tiếp tìm được. Nếu không có cây nào có khối lượng mận thỏa mãn sức chứa của gùi, in ra .
Ví dụ:
Dữ liệu:
4 5
3 1 2 1
Kết quả:
3
Dữ liệu:
3 3
4 10 2
Kết quả:
1
Giải thích:
Ở ví dụ 1: Các bạn có thể hái từ cây thứ 2 đến cây thứ 4 (dãy ), tổng khối lượng là , số lượng cây là .
Ở ví dụ 2: Cây thứ 1 và thứ 2 đều có khối lượng lớn hơn 3, chỉ có cây cuối cùng thỏa mãn, số lượng cây lớn nhất là .
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (30% số điểm): .
Subtask #3 (15% số điểm): và với mọi .
Subtask #4 (35% số điểm): , không có ràng buộc gì thêm về .
