첫 출하량을 채우는 날

문제

한 농장은 수확한 작물을 상자에 담아 공동 보관실에 모은다. 농장에서는 첫 출하에 사용할 상자를 적어도 G개 확보하려 한다. 이를 위해 앞으로 N일 동안 매일 작업을 마친 뒤, 그날 새로 보관실에 넣은 상자 수를 장부에 기록한다. 비가 오거나 포장 작업을 쉬는 날에는 새로 넣는 상자가 없을 수 있다. 관찰을 시작하기 직전에는 보관실에 상자가 하나도 없다. i일째에는 장부에 적힌 a_i개의 상자를 기존 상자에 더한다. 관찰하는 동안 상자를 밖으로 꺼내거나 버리는 일은 없으며, 앞선 날에 넣은 상자는 모두 그대로 남아 있다. 따라서 어떤 날의 작업이 끝났을 때 보관실에 있는 상자 수는 첫날부터 그날까지 넣은 상자 수를 모두 더한 값이다. 농장 관리자는 작업이 끝난 시점의 상자 수가 처음으로 G개 이상이 되는 날을 알고 싶다. 정확히 G개가 되는 날도 목표를 채운 날로 본다. 한꺼번에 많은 상자가 들어와 G개를 넘어가더라도, 그날을 목표를 채운 날로 기록한다. 목표를 채운 다음 날의 기록은 최초 달성일에 영향을 주지 않는다. 날짜는 관찰을 시작한 날부터 1일째, 2일째와 같이 센다. 첫날에 목표를 채웠다면 답은 1이다. N일 동안 모은 상자를 모두 합해도 G개보다 적다면 관찰 기간 안에는 목표를 채운 날이 없는 것으로 처리한다. 장부에는 N일의 기록이 빠짐없이 주어지며, 기록 순서는 날짜 순서와 같다. 목표를 처음 채운 날짜를 출력하고, 그런 날짜가 없으면 -1을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 G가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000이고 1 ≤ G ≤ 1,000,000이다.
둘째 줄에 정수 a_1, a_2, …, a_N이 날짜 순서대로 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ a_i ≤ 1,000이다.

출력

작업이 끝난 뒤 누적 상자 수가 처음으로 G 이상이 되는 날짜를 정수 하나로 출력한다. 해당 날짜가 없으면 -1을 출력한다.

5 17
3 0 8 6 4

4

4 9
2 2 2 2

-1

1 1
1

1

출처: Devin.KR 자체 제작