First Budget Exceedance

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

A person has a budget of $B$ and records $n$ expenses in chronological order. The $i$-th expense costs $a_i$. The cumulative cost after expense $i$ is $S_i=a_1+a_2+\cdots+a_i$. Find the first 1-based position $i$ such that $S_i>B$. If no expense makes the cumulative cost exceed the budget, print $-1$. When $n=0$, there are no expenses.

Input

The first line contains two integers $n$ and $B$: the number of expenses and the budget. If $n>0$, the following input contains $n$ non-negative integers $a_1,a_2,\ldots,a_n$ in chronological order, separated by whitespace and possibly spread across multiple lines. If $n=0$, no $a_i$ follows.

Output

Print one integer: the smallest position $i$ with $S_i>B$, or $-1$ if none exists.

Subtasks

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

Examples

Example 1

Input:

4 10
3 2 6 1

Output:

3

Explanation: The first three cumulative costs are $3$, $5$, and $11$. Since $11>10$ and the earlier totals are not above $10$, the first position is $3$.

Example 2

Input:

3 10
4 6 0

Output:

-1

Explanation: The cumulative costs are $4$, $10$, and $10$. Equality with the budget is not an exceedance. No valid position exists.

Example 3

Input:

0 0

Output:

-1

Explanation: There are no expenses, so no position can exceed the budget.