여과기 점검표의 동그라미

문제

수족관의 관리인은 여과기가 처리한 물의 양을 확인하기 위해 새 점검표를 만들었다. 점검표에는 날짜별 가동 시간과 함께, 점검을 시작한 뒤 처리한 물의 누적량을 적는다. 여과기는 가동 중에 매분 정확히 R리터의 물을 처리하며, 날짜가 바뀌어도 처리 속도는 달라지지 않는다. 가동하지 않은 시간에는 물을 처리하지 않는다. 점검은 1일째부터 N일째까지 이어진다. i일째에 여과기를 가동한 시간은 정수 A_i분이다. 하루 동안 여러 번 나누어 가동했더라도 그날 가동한 시간을 모두 더한 값이 A_i로 주어진다. 따라서 그날 처리한 물의 양은 R과 A_i를 곱한 값이다. 가동 시간이 0분인 날도 점검표에 포함하며, 이러한 날에는 전날까지의 누적량이 그대로 유지된다. 점검을 시작하기 직전의 누적량은 0리터다. 관리인은 매일 가동을 모두 마친 뒤 그날까지의 누적량을 확인한다. 누적량이 목표인 G리터 이상이 된 날이 있으면, 그러한 날 중 가장 이른 날의 칸에만 동그라미를 하나 그린다. 목표와 정확히 같아진 경우에도 동그라미를 그린다. 동그라미를 그린 뒤에도 남은 날짜의 가동 기록은 계속 작성한다. 이 점검표의 누적량은 여과기를 통과한 물의 양을 모두 더한 값이다. 같은 물이 여과기를 다시 통과하더라도 처리한 양에 다시 포함한다. 따라서 수족관에 담긴 물의 전체 양을 따로 고려할 필요는 없다. 또한 이전 점검표에 적힌 처리량은 이번 점검에 포함하지 않는다. N일 동안의 가동 기록이 주어질 때, 동그라미가 그려지는 날의 번호를 구한다. 날짜 번호는 1부터 시작한다. 마지막 날까지 목표에 도달하지 못했다면 동그라미를 그리지 않은 것으로 처리한다.

입력

첫째 줄에 정수 N, R, G가 공백으로 구분되어 주어진다. N은 점검 일수, R은 여과기가 매분 처리하는 물의 양, G는 목표 처리량이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
제약은 1 ≤ N ≤ 1,000, 1 ≤ R ≤ 1,000, 1 ≤ G ≤ 1,000,000,000, 0 ≤ A_i ≤ 1,000이다. 모든 입력값은 정수다.

출력

누적 처리량이 G리터 이상이 되는 가장 이른 날의 번호를 정수 하나로 출력한다. 그러한 날이 없으면 0을 출력한다.

5 7 100
3 4 0 8 2

4

4 3 40
0 4 4 5

0

1 10 20
2

1

출처: Devin.KR 자체 제작