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

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

요약

가능한 한 늦게 시작하려면 며칠 차부터 다이어트를 시작할 때 감소량 합이 M 이상이 되는지 구하고, 불가능하면 -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
```