Lần đầu vượt ngân sách (First Budget Exceedance)

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

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

Đề bài

Một người có ngân sách $B$ đồng và ghi lại $n$ khoản chi theo thứ tự phát sinh. Khoản chi thứ $i$ có giá trị $a_i$ đồng. Tổng tiền đã chi sau khoản thứ $i$ là $S_i=a_1+a_2+\cdots+a_i$. Hãy tìm vị trí đầu tiên $i$ sao cho $S_i>B$. Vị trí các khoản chi được đánh số từ $1$. Nếu chưa có khoản chi nào làm tổng vượt ngân sách, hãy in $-1$. Khi $n=0$, không có khoản chi nào.

Input

Dòng đầu chứa hai số nguyên $n$ và $B$, lần lượt là số khoản chi và ngân sách. Nếu $n>0$, dòng tiếp theo chứa $n$ số nguyên không âm $a_1,a_2,\ldots,a_n$ theo đúng thứ tự phát sinh. Các số có thể nằm trên nhiều dòng và được phân cách bằng khoảng trắng. Với $n=0$, không có số $a_i$.

Output

In một số nguyên: vị trí nhỏ nhất $i$ có $S_i>B$, hoặc $-1$ nếu không tồn tại.

Subtask

• Subtask 1 (20%): $0\le n\le20,\ 0\le B\le10^9,\ 0\le a_i\le10^9$.
• Subtask 2 (30%): $0\le n\le1000,\ 0\le B\le10^9,\ 0\le a_i\le10^9$.
• Subtask 3 (50%): $0\le n\le10^5,\ 0\le B\le10^9,\ 0\le a_i\le10^9$.

Ví dụ

Ví dụ 1

Input:

4 10
3 2 6 1

Output:

3

Giải thích: Sau khoản $1$ tổng là $3$; sau khoản $2$ tổng là $5$; sau khoản $3$ tổng là $11$. Vì $11>10$ và hai tổng trước không vượt $10$, vị trí đầu tiên là $3$.

Ví dụ 2

Input:

3 10
4 6 0

Output:

-1

Giải thích: Các tổng lần lượt là $4$, $10$, $10$. Tổng bằng ngân sách không phải vượt ngân sách. Vì vậy không có vị trí thỏa mãn và in $-1$.

Ví dụ 3

Input:

0 0

Output:

-1

Giải thích: Không có khoản chi nào để xét nên không thể tồn tại vị trí có tổng vượt ngân sách.