Sequential Task Scheduling with Daily Sleep Constraint

Eric has n tasks to complete in order. The i-th task takes t_i time. He must do the tasks sequentially and the time to finish each task must be continuous (i.e. it cannot be split between days).

Each day has a total of x time. However, Eric must sleep every day. His sleep time each day is a continuous block, and after his sleep ends, the next day starts immediately. Moreover, for the first i days, the total sleep time must be at least \(r \times x \times i\) (in other words, the average sleep time per day must be at least \(r \times x\)).

Assuming Eric can choose his daily sleep time on each day optimally (i.e. minimizing sleep while satisfying the constraint), determine the minimum number of days needed to complete all tasks.

Note: It is guaranteed that each individual task can be completed within the available working time in one day.

Hint: The optimal strategy is to sleep exactly \(r\times x\) each day so that the working period per day is maximized to \(x(1-r)\). You then assign tasks in order into these available slots (keeping in mind that each task must be completed wholly within one day).

inputFormat

The first line contains three numbers: n, x, and r, where n is the number of tasks, x is the total time in one day, and r is a real number representing the fraction requirement for sleep.

The second line contains n space‐separated numbers: t₁, t₂, ..., t_n, where t_i is the time needed for the i-th task.

outputFormat

Output a single integer — the minimum number of days needed for Eric to finish all tasks.

sample

5 10 0.2
3 4 2 6 1

3