Trucks

A single lane bridge crosses a river. $n$ trucks cross it in the given order. The order cannot be changed, and the trucks do not all weigh the same.

The bridge is $w$ units long, so at most $w$ trucks stand on it at the same time. Each truck moves exactly one unit of distance per unit of time. The total weight of the trucks that are on the bridge at any moment must be at most the maximum load $L$. A truck that has not yet moved completely onto the bridge does not count toward that total.

Figure 1 shows four trucks with weights 7, 4, 5, 6 crossing from right to left when the bridge length $w$ is 2 and the maximum load $L$ is 10. The shortest time for all of them to cross is 8.

Figure 1. Trucks crossing the bridge.

Given the bridge length, the maximum load, and the weights of the trucks in crossing order, write a program that computes the shortest time for every truck to finish crossing.

Input comes from standard input and has two lines.

The first line contains three integers $n$, $w$, and $L$ separated by spaces. $n$ is the number of trucks, $w$ is the length of the bridge, and $L$ is the maximum load of the bridge ($1 \le n \le 1000$, $1 \le w \le 100$, $10 \le L \le 1000$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces. $a_i$ is the weight of the $i$-th truck ($1 \le a_i \le 10$).

Print to standard output the shortest time for all trucks to cross the bridge, on one line.