Problem C
Concert Rehearsal

Weill Recital Hall, Carnegie Hall, Photo by Nat Welch

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?

Input

The first line of input contains three integers $n$, $p$, $k$ ($1 \le n \le 2 \cdot 10^5, 1 \leq p, k \leq 10^9$). Each of the next $n$ lines contains a single integer. The $i$th line gives $d_ i$ ($1 \leq d_ i \leq p$).

Output

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

3 9 5
1
2
3

7

4 10 5
3
2
4
6

2

3 10 2
5
6
7

0