Raehwan's Mission to Get a Girlfriend

Interview

Time limit1sMemory limit1024 MB

Summary

Given daily weight losses A_i, find the latest start day s such that dieting every day from s through N loses at least M units, or -1 if no start day works.

Level: Easy3 of 10
Topics: Prefix sum, Two pointers
Solved: No attempts yet

Problem

Raehwan has a blind date $N$ days from now, and he wants to find a girlfriend. He decides to lose $M$ units of weight through a diet. Raehwan knows in advance the weight loss $A_i$ from dieting on day $i$ ( $i = 1, 2, \cdots, N$ ). Because he keeps a regular routine, his weight does not change on days when he does not diet.

Find the latest day on which he can start his diet and still reach his goal before the blind date.

Input

The first line contains two integers $N$ ( $1 \le N \le 10^5$ ) and $M$ ( $1 \le M \le 10^9$ ), separated by a space.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ , separated by spaces. ( $1 \le A_i \le 10^4$ )

Output

Print the day number from which Raehwan should start his diet so that he postpones it as long as possible and still reaches his goal. If the diet can never succeed, print $-1$ instead.

Examples2

Example 1
Input
```
4 7
5 4 2 2
```
Expected output
```
2
```
Example 2
Input
```
5 6
1 1 1 1 1
```
Expected output
```
-1
```