반납 책 수레의 목표선

문제

도서관에서는 반납된 책을 작은 수레에 모은 뒤 서가로 옮긴다. 사서는 수레를 출발시키기 전에 책이 얼마나 모이는지 알아보기 위해 반납 창구에서 들어오는 책의 수를 차례대로 기록했다. 기록 하나는 한 번에 창구로 들어온 책 묶음에 해당하며, 각 기록에는 그 묶음에 들어 있는 책의 수가 적혀 있다. 조사를 시작할 때 수레는 비어 있다. 사서는 첫 번째 기록부터 마지막 기록까지 순서대로 확인하면서, 각 기록에 적힌 수만큼 책을 수레에 추가한다. 이 조사에서는 중간에 책을 꺼내거나 다른 수레로 옮기지 않는다. 따라서 어떤 기록을 처리한 직후 수레에 있는 책의 수는 첫 번째 기록부터 그 기록까지 들어온 책의 수를 모두 더한 값이다. 사서는 수레에 있는 책이 목표 권수 K 이상이 되는 순간을 찾으려 한다. 기록을 하나 처리할 때마다 그 직후의 책 수를 확인하며, 목표 권수와 정확히 같아진 경우에도 목표에 도달한 것으로 본다. 한 묶음 때문에 목표 권수를 넘어가더라도 책을 나누어 담지 않고 그 기록 전체를 처리한 것으로 본다. 책이 한 권도 들어오지 않은 기록도 있으며, 이런 기록 역시 순서 번호에 포함된다. 기록의 순서 번호는 1부터 N까지다. 목표에 처음 도달한 뒤에도 남은 기록은 입력에 그대로 주어지지만, 구하려는 번호는 달라지지 않는다. 모든 기록을 처리한 뒤에도 수레의 책 수가 K보다 작다면 목표에 도달하지 못한 것이다. 주어진 기록을 이용하여 수레의 책 수가 처음으로 K 이상이 되는 기록의 순서 번호를 구한다. 목표에 도달하는 기록이 없다면 0을 출력한다.

입력

첫째 줄에 기록의 수 N과 목표 권수 K가 공백으로 구분되어 주어진다. 둘째 줄에 기록 순서대로 책의 수 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000, 0 ≤ a_i ≤ 1,000이다.

출력

수레의 책 수가 처음으로 K 이상이 되는 기록의 순서 번호를 정수 하나로 출력한다. 그런 기록이 없으면 0을 출력한다.

6 13
3 0 4 6 2 1

4

4 12
2 3 0 6

0

1 7
9

1

출처: Devin.KR 자체 제작