목표 거리를 넘긴 기록

문제

마라톤 대회 운영팀은 참가자 한 명의 이동 기록을 차례대로 확인하고 있다. 기록 장치는 출발 이후의 시간을 여러 구간으로 나누고, 각 구간에서 참가자가 앞으로 이동한 거리를 정수 미터 단위로 남긴다. 운영팀이 확인하려는 목표 거리는 D미터이다. 참가자는 첫 번째 구간이 시작되기 직전에 출발점에 있으며, 이때 누적 이동 거리는 0미터이다. 각 기록에 적힌 값은 그 구간에서 새로 이동한 거리이다. 출발점부터 해당 구간이 끝날 때까지의 전체 거리가 아니므로, 누적 이동 거리를 알아내려면 앞선 구간들의 거리를 함께 더해야 한다. 참가자가 쉬거나 제자리에서 기다린 구간의 기록은 0일 수 있다. 뒤로 이동하는 경우는 없으므로 음수 기록은 주어지지 않는다. 모든 기록은 시간 순서대로 주어진다. 운영팀은 각 구간이 끝나는 순간에만 누적 이동 거리를 확인한다. 누적 이동 거리가 처음으로 D 이상이 된 구간의 번호를 찾으려 한다. 누적 거리가 정확히 D가 된 경우도 목표를 달성한 것으로 본다. 한 구간에서 목표 거리를 지나쳤더라도 그 구간의 번호를 사용하며, 구간 안에서 목표를 통과한 시각이나 위치는 계산하지 않는다. 구간 번호는 입력 순서대로 1부터 N까지 붙인다. 목표를 달성한 뒤에 다른 기록이 더 주어져도 최초로 달성한 구간의 번호는 바뀌지 않는다. 마지막 구간까지 모두 더한 거리가 D보다 작다면 목표를 달성하지 못한 것이다. 주어진 기록 전체를 바탕으로 최초 달성 구간의 번호를 구한다. 출력할 번호는 하나뿐이며, 목표를 달성하지 못했다면 정해진 값 -1을 출력한다.

입력

첫째 줄에 구간 수 N과 목표 거리 D가 공백으로 주어진다. N과 D는 정수이며 1≤N≤1,000, 1≤D≤1,000,000이다.
둘째 줄에 각 구간에서 새로 이동한 거리를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 i에 대하여 0≤A_i≤1,000이다. 거리의 단위는 미터이다.

출력

누적 이동 거리가 처음으로 D 이상이 된 구간의 번호를 한 줄에 출력한다. 모든 구간이 끝나도 목표를 달성하지 못했다면 -1을 출력한다.

5 12
3 0 4 5 8

4

4 20
5 4 0 10

-1

3 7
9 0 2

1

출처: Devin.KR 자체 제작