목표 상자를 채운 날

문제

작은 공장의 생산 라인에서는 매일 완성한 부품을 검사한 뒤, 검사를 통과한 부품만 출하 준비 상자에 넣는다. 작업자는 앞으로 N일 동안 상자에 넣은 부품의 수를 날짜 순서대로 기록했다. 기록에는 검사를 통과한 부품만 포함되어 있으므로, 불량 부품의 수를 따로 빼거나 생산량을 다시 계산할 필요는 없다. 생산 라인이 멈춘 날에는 기록된 수가 0일 수도 있다. 이번 출하에 필요한 부품의 수는 K개이다. 첫째 날의 작업을 시작하기 직전에는 상자가 비어 있다. 하루의 작업이 끝나면 그날 기록된 수만큼 부품이 상자에 추가된다. 상자에 들어간 부품은 기록된 N일 동안 꺼내지 않으며, 다른 곳에서 부품을 가져와 추가하는 일도 없다. 따라서 어떤 날의 작업이 끝난 뒤 상자에 있는 부품의 수는 첫째 날부터 그날까지 기록된 수를 모두 더한 값이다. 공장은 하루의 작업이 끝날 때만 출하 준비 여부를 확인한다. 상자에 든 부품의 수가 K개 이상이면 목표를 달성한 것으로 본다. 정확히 K개가 되어도 목표를 달성한 것이며, 하루 생산량 때문에 K개를 넘어가도 그날 목표를 달성한 것으로 처리한다. 한 번 목표를 달성한 뒤의 기록은 최초 달성 날짜를 바꾸지 않는다. 날짜에는 첫째 날부터 차례대로 1, 2, …, N의 번호를 붙인다. 주어진 기록을 이용하여 목표를 처음 달성한 날짜의 번호를 구한다. N일의 작업이 모두 끝나도 상자에 든 부품이 K개보다 적다면 목표를 달성한 날짜가 없으므로 -1을 출력한다.

입력

첫째 줄에 기록된 날짜 수 N과 목표 부품 수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000이다.
둘째 줄에 날짜 순서대로 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. A_i는 i번째 날에 상자에 추가한 부품의 수이며 0 ≤ A_i ≤ 1,000이다.

출력

누적 부품 수가 처음으로 K 이상이 되는 날짜의 번호를 정수 하나로 출력한다. 그런 날짜가 없으면 -1을 출력한다.

5 12
3 0 4 6 2

4

3 10
2 3 4

-1

1 1
1

1

출처: Devin.KR 자체 제작