24579번 - Concert Rehearsal 다국어

A class of n music students are going to rehearse for a concert in a recital hall. In one rehearsal pass, each student will give one performance in order from student 1 to student n. Student i’s performance has a duration of d_i. After the last student’s performance concludes, a new rehearsal pass will start immediately, beginning with the performance of student 1.

On each day, the recital hall will be open for a fixed duration of p. At any moment if the next student’s performance cannot complete before the recital hall closes, all the remaining performances within the current rehearsal pass will be moved to the next day.

In k days, how many full rehearsal passes can the class complete?

The first line of input contains three integers n, p, k (1 ≤ n ≤ 2 · 10⁵, 1 ≤ p, k ≤ 10⁹). Each of the next n lines contains a single integer. The ith line gives d_i (1 ≤ d_i ≤ p).

Output the number of full rehearsal passes the class can complete in k days.