관측 기록의 첫 도달일

문제

한 날씨 관측소는 비가 내린 양을 하루에 한 번씩 정수로 기록한다. 관측 담당자는 새로운 조사 기간이 시작되면 누적 강수량을 0으로 놓고, 매일 관측을 마친 뒤 그날의 강수량을 누적 강수량에 더한다. 조사 기간의 날짜는 시작일부터 차례대로 1일, 2일, …, N일로 부른다. 하루의 강수량이 0일 수도 있으며, 이런 날에도 날짜는 하루가 지난 것으로 센다. 관측소는 조사 전에 목표 강수량 K를 정한다. 조사 기간 중 누적 강수량이 K 이상이 되는 날이 있으면, 그중 가장 이른 날을 보고서에 적으려고 한다. 목표와 정확히 같아진 날도 목표에 도달한 날에 포함한다. 어떤 날 목표에 도달했더라도 다음 날부터 누적 강수량을 다시 0으로 바꾸지는 않는다. 이 문제에서 사용하는 누적 강수량은 언제나 조사 시작일부터 해당 날짜까지 기록된 강수량의 합이다. 하루에 기록된 강수량만으로 목표 도달 여부를 판단해서는 안 된다. 예를 들어 전날까지의 누적 강수량이 목표보다 작더라도, 오늘의 강수량을 더한 결과가 목표 이상이면 오늘이 도달일이 될 수 있다. 반대로 여러 날의 누적 강수량이 모두 목표 이상이라면 그 날짜들을 전부 출력하는 것이 아니라 최초의 날짜 하나만 출력한다. N일 동안의 강수량 기록과 목표 강수량이 주어진다. 각 기록은 시간순으로 주어지며, 빠진 날짜나 같은 날짜의 중복 기록은 없다. 모든 강수량의 단위는 같고 단위 변환은 필요하지 않다. 조사 기간 안에 목표에 처음 도달한 날짜를 구한다. 마지막 날의 관측을 마친 뒤에도 누적 강수량이 목표보다 작으면 -1을 출력한다.

입력

첫째 줄에 조사 기간 N과 목표 강수량 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000이다.
둘째 줄에 1일부터 N일까지의 강수량 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 A_i는 정수이며 0 ≤ A_i ≤ 1,000이다.

출력

누적 강수량이 K 이상이 되는 가장 이른 날짜를 정수 하나로 출력한다. 그런 날짜가 없으면 -1을 출력한다.

5 12
3 0 5 4 9

4

4 9
2 2 2 2

-1

3 5
5 0 5

1

출처: Devin.KR 자체 제작