Dừng khi vượt hạn mức (Stop Before Exceeding the Budget)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bạn có hạn mức $B$ và nhận tuần tự $n$ khoản chi không âm. Chỉ nhận một đoạn đầu liên tiếp của dãy: trước mỗi khoản, nếu cộng khoản đó khiến tổng vượt $B$ thì dừng ngay và không nhận khoản ấy cũng như không xét các khoản sau. Nếu tổng sau cộng đúng bằng $B$, khoản đó vẫn được nhận. Hãy in số khoản đã nhận; nếu khoản đầu tiên vượt mức hoặc $n=0$, kết quả bằng 0.

Input

Đọc $n,B$, rồi đúng $n$ khoản chi nguyên $a_i$. $0\le n\le100000$, $0\le B\le10^{12}$, $0\le a_i\le10^9$.

Output

In một số nguyên: số khoản đã nhận trước khi dừng.

Subtask

• Subtask 1 (20%): $0\le n\le 8$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

• Subtask 2 (30%): $0\le n\le 1000$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

• Subtask 3 (50%): $0\le n\le 100000$; ngưỡng/hạn mức đến $10^{12}$; mỗi số từ $0$ đến $10^9$.

Ví dụ

Ví dụ 1

Input:

4 10
3 5 4 1

Output:

2

Giải thích:

nhận khoản 1 (3), tổng 3; nhận khoản 2 (5), tổng 8; khoản 3 (4) làm tổng thành 12>10, dừng trước khi nhận. Số khoản đã nhận là 2.

Ví dụ 2

Input:

3 8
3 5 0

Output:

3

Giải thích:

nhận khoản 1 (3), tổng 3; nhận khoản 2 (5), tổng 8; nhận khoản 3 (0), tổng 8. Số khoản đã nhận là 3.