주말 꾸러미를 위한 보관함

문제

한 편의점에서는 주말에 나누어 줄 간식 꾸러미를 준비하고 있다. 꾸러미에 넣을 간식은 다른 판매용 상품과 구분하여 전용 보관함에 모은다. 준비를 시작하기 전에는 보관함이 비어 있으며, 준비 기간은 모두 N일이다. 날짜에는 첫날부터 차례대로 1번부터 N번까지 번호를 붙인다. 직원은 매일 영업을 마친 뒤 그날 따로 마련한 간식을 보관함에 넣는다. i번 날에 넣는 간식의 개수는 A_i개다. 간식을 하나도 마련하지 못한 날에는 아무것도 넣지 않으며, 이때 A_i는 0이다. 한번 넣은 간식은 준비 기간 동안 꺼내거나 판매하지 않는다. 따라서 하루가 끝났을 때 보관함에 있는 간식의 개수는 전날까지 모은 개수에 그날 넣은 개수를 더한 값이다. 꾸러미 준비에 필요한 간식은 모두 K개다. 직원은 매일 그날의 간식을 모두 넣은 직후에 보관함을 확인한다. 보관함에 있는 간식이 K개 이상이면 필요한 수량을 확보한 것으로 판단한다. 정확히 K개가 된 경우도 포함하며, 한꺼번에 여러 개를 넣어 K개를 넘어선 경우에도 그날 필요한 수량을 확보한 것이다. 하루 도중의 상황은 따로 고려하지 않는다. 직원이 알고 싶은 것은 필요한 수량을 처음 확보한 날짜의 번호다. 예를 들어 어떤 날까지 모은 개수가 K보다 작고 다음 날의 간식을 넣은 뒤 K개 이상이 되었다면, 다음 날의 번호가 답이다. 그 뒤에도 간식이 추가될 수 있지만 처음 확보한 날짜는 바뀌지 않는다. 여러 날에 걸쳐 K개 이상을 보관하더라도 가장 이른 날짜 하나만 출력한다. 준비 기간의 마지막 날까지 모은 간식이 K개보다 적을 수도 있다. 이 경우에는 필요한 수량을 확보한 날이 없으므로 -1을 출력한다. N일 동안 매일 넣은 간식의 개수가 주어질 때, 필요한 수량을 처음 확보한 날짜의 번호를 구하는 프로그램을 작성하라.

입력

첫째 줄에 준비 기간 N과 필요한 간식의 개수 K가 공백으로 구분되어 주어진다.
둘째 줄에 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000, 0 ≤ A_i ≤ 1,000이다.

출력

보관함의 간식이 처음으로 K개 이상이 되는 날짜의 번호를 정수 하나로 출력한다. 해당하는 날짜가 없으면 -1을 출력한다.

5 12
3 0 4 6 2

4

4 9
2 2 2 2

-1

3 7
7 0 4

1

출처: Devin.KR 자체 제작