Stop Before Exceeding the Budget

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given budget $B$ and $n$ nonnegative expenses in order, accept the longest initial prefix whose running total never exceeds $B$. Stop before the first expense that would exceed $B$; do not skip it to examine later expenses. Equality with $B$ is allowed. Print the number accepted.

Input

Read $n,B$, then exactly $n$ integer expenses $a_i$. $0\le n\le100000$, $0\le B\le10^{12}$, $0\le a_i\le10^9$.

Output

Print the number of expenses accepted before stopping.

Subtasks

• Subtask 1 (20%): $0\le n\le 8$; threshold/budget up to $10^{12}$; values from $0$ to $10^9$.

• Subtask 2 (30%): $0\le n\le 1000$; threshold/budget up to $10^{12}$; values from $0$ to $10^9$.

• Subtask 3 (50%): $0\le n\le 100000$; threshold/budget up to $10^{12}$; values from $0$ to $10^9$.

Examples

Example 1

Input:

4 10
3 5 4 1

Output:

2

Explanation:

Budget 10; accept the initial expenses until the first one that would exceed it. Accepted count: 2.

Example 2

Input:

3 8
3 5 0

Output:

3

Explanation:

Budget 8; accept the initial expenses until the first one that would exceed it. Accepted count: 3.