수족관의 급여 기록

문제

수족관에서는 관찰 중인 물고기 무리에게 매일 먹이 알갱이를 나누어 준다. 사육 담당자는 관찰을 시작한 뒤 지급한 먹이의 누적 개수가 목표에 도달하는 날을 기록하려 한다. 하루에 지급하는 먹이는 많아도 아홉 개이므로, 담당자는 하루의 지급량을 숫자 한 글자로 적어 여러 날의 기록을 하나의 문자열로 보관했다. 기록의 첫 번째 문자는 관찰 첫째 날의 지급량을 뜻하고, 두 번째 문자는 둘째 날의 지급량을 뜻한다. 같은 방식으로 i번째 문자는 i번째 날의 지급량을 뜻한다. 문자 0은 그날 먹이를 지급하지 않았다는 뜻이다. 기록에는 날짜 사이를 구분하는 공백이나 다른 기호가 들어 있지 않으며, 앞부분에 있는 0도 실제 날짜 하나를 나타내므로 생략하면 안 된다. 첫째 날이 시작하기 전의 누적 지급량은 0이다. 매일 그날의 먹이를 모두 지급한 직후, 첫째 날부터 그날까지 지급한 먹이의 개수를 합산한다. 이 합이 목표 개수 T 이상이 되는 날 중 가장 이른 날을 찾아야 한다. 누적 지급량이 T와 정확히 같아야 하는 것은 아니며, 하루의 지급으로 T를 넘어가도 목표에 도달한 것으로 본다. 먹이를 물고기가 먹었는지와 관계없이 지급한 개수만 누적한다. 관찰 도중 누적 지급량을 줄이거나 다시 0으로 만드는 일은 없다. 주어진 N일의 기록을 모두 확인해도 목표에 도달하지 못할 수 있으며, 이 경우에는 정해진 특별한 값을 출력한다. 날짜는 첫째 날을 1로 세며, 목표에 처음 도달한 뒤의 기록은 답에 영향을 주지 않는다.

입력

첫째 줄에 기록한 날짜 수 N과 목표 개수 T가 공백으로 구분되어 주어진다. N과 T는 정수이며 1 ≤ N ≤ 100,000, 1 ≤ T ≤ 900,001이다.
둘째 줄에 숫자 0부터 9로만 이루어진 길이 N의 문자열이 주어진다. i번째 숫자는 i번째 날에 지급한 먹이의 개수다.

출력

누적 지급량이 처음으로 T 이상이 되는 날짜를 정수 하나로 출력한다. N일 동안 목표에 도달하지 못하면 -1을 출력한다.

6 10
032504

4

4 1
0000

-1

3 18
909

3

출처: Devin.KR 자체 제작