래환이의 여자친구 사귀기 대작전

면접 대비

시간 제한1초메모리 제한1024 MB

요약

매일 감량량 A_i가 주어질 때, s일부터 N일까지 매일 다이어트하여 M 이상을 감량할 수 있는 가장 늦은 시작일 s를 구합니다. 가능한 시작일이 없으면 -1을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 투 포인터
정답자: 아직 제출이 없습니다

문제

래환이는 여자친구를 만들기 위해 $N$ 일 뒤에 소개팅에 나간다. 여자친구를 사귀고 싶은 래환이는 다이어트로 체중을 $M$ 만큼 빼기로 결심했다. 래환이는 $i$ 일차에 다이어트를 했을 때의 체중 감소량 $A_i$ 를 미리 알고 있다. ( $i = 1, 2, \cdots, N$ ) 래환이는 규칙적으로 생활하기 때문에 다이어트를 하지 않는 날에는 체중이 변하지 않는다.

래환이가 다이어트를 최대한 미루면서도 소개팅 전에 목표를 달성할 수 있는 시작 날짜를 구한다.

입력

첫 번째 줄에 두 정수 $N$ ( $1 \le N \le 10^5$ )과 $M$ ( $1 \le M \le 10^9$ )이 공백으로 구분되어 주어진다.

두 번째 줄에 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다. ( $1 \le A_i \le 10^4$ )

출력

다이어트를 최대한 미뤄서 목표를 달성하려면 몇 일차부터 다이어트를 시작해야 하는지 출력한다. 다이어트가 절대 성공할 수 없다면 대신 $-1$ 을 출력한다.

예제2

예제 1
입력
```
4 7
5 4 2 2
```
예상 출력
```
2
```
예제 2
입력
```
5 6
1 1 1 1 1
```
예상 출력
```
-1
```