First Prefix Reaching a Threshold

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ nonnegative integers and a positive threshold $T$, find the smallest 1-based index $i$ whose prefix sum is at least $T$. Print -1 if the threshold is never reached. The order of input matters.

Input

The first two integers are $n,T$, followed by exactly $n$ nonnegative integers. $1\le n\le100000$, $1\le T\le10^{12}$, $0\le a_i\le10^9$.

Output

Print the first 1-based position whose prefix sum is at least $T$, or -1.

Subtasks

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

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

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

Examples

Example 1

Input:

4 8
3 5 1 2

Output:

2

Explanation:

Threshold 8; prefix sums by index: 1→3, 2→8. The answer is 2.

Example 2

Input:

3 20
3 5 1

Output:

-1

Explanation:

Threshold 20; prefix sums by index: 1→3, 2→8, 3→9. The answer is -1.