Trucks

Interview

Time limit1sMemory limit512 MB

Summary

Trucks cross a one-lane bridge in order under a weight limit; find the earliest time all have finished.

Level: Easy3 of 10
Topics: Queue, Simulation
Solved: No attempts yet

Problem

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

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$ ).

Output

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

Examples4

Example 1
Input
```
4 2 10
7 4 5 6
```
Expected output
```
8
```
Example 2
Input
```
1 100 100
10
```
Expected output
```
101
```

Example 3

Input

10 100 100
10 10 10 10 10 10 10 10 10 10

Expected output

Example 4
Input
```
1 1 10
1
```
Expected output
```
2
```