Câu 4 (3,0 điểm). Hành trình xe điện

Để nâng cao hiệu suất vận hành cho một loại xe điện mới, các bạn trong nhóm START UP đã tiến hành thử nghiệm như sau:

Một tuyến đường được chia làm \(N\) chặng đường liên tiếp, khi xe điện chạy ở chặng thứ \(i\) của con đường, xe điện sẽ tiêu thụ một lượng \(a_i\) đơn vị năng lượng (\(a_i > 0\)) hoặc được nạp thêm một lượng \(a_i\) năng lượng nhờ hệ thống tái tạo năng lượng khi đường xuống dốc (\(a_i < 0\)). Một hành trình liên tiếp sẽ xuất phát từ chặng thứ \(i\) và kết thúc tại chặng thứ \(j\) (\(1 \leq i \leq j \leq N\)), khi đó tổng năng lượng trên hành trình đó là: \(a_i + a_{i+1} + \dots + a_j\).

Các bạn mong muốn tìm một hành trình liên tiếp dài nhất để thử nghiệm, tuy nhiên để đảm bảo an toàn cho pin và các thiết bị khác trên xe, tổng năng lượng trên một hành trình liên tiếp không được vượt quá giới hạn an toàn \(P\) của pin.

Yêu cầu: Hãy xác định số chặng đường liên tiếp dài nhất sao cho tổng các giá trị năng lượng trên đoạn đó không vượt quá giới hạn an toàn \(P\) của pin.

Input

Dữ liệu vào: Cho tệp văn bản CAU4.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên \(N\) và \(P\) (\(1 \leq N \leq 5 \times 10^5; P \leq 10^9\));
• Dòng 2: Chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \leq a_i \leq 10^9\)).

Các số trên cùng một dòng được ghi cách nhau bởi một dấu cách.

Output

Kết quả: Ghi ra tệp văn bản CAU4.OUT gồm một dòng ghi ra độ dài lớn nhất của chặng đường liên tiếp theo yêu cầu của bài toán. Biết rằng, dữ liệu đầu vào luôn đảm bảo tìm ra kết quả.

Example

5 7
8 2 2 4 1

3

Scoring

Ràng buộc:

• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 1000, -10^4 \leq a_i \leq 10^4\);
• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 10^5, 0 \leq a_i \leq 10^9\);
• Có \(1/3\) số test tương ứng \(1/3\) số điểm của bài với \(N \leq 5 \times 10^5, -10^9 \leq a_i \leq 10^9\).