P1594 Escort Convoy

An escort convoy lines up on a one-way street approaching a one-lane bridge over a river. Because the street is one-way, no vehicle can overtake another. The bridge can bear a given maximum load. To control traffic on the bridge, there is a dispatcher at each end. The convoy is divided into several groups, and all vehicles in the same group can enter the bridge at the same time. When a group reaches the other end of the bridge, the dispatcher at that end phones the dispatcher at the starting end so that the next group may begin to cross. Each vehicle’s weight is known. The total weight of any group must not exceed the bridge’s maximum load. Every vehicle in the same group crosses at its own top speed. The time for a group to cross the bridge is determined by the time needed for the slowest vehicle in that group to cross. The task is to compute the minimum total time for the entire convoy to cross the bridge.

The first line contains three integers: the bridge’s maximum load (in tons), the bridge length (in kilometers), and the total number of vehicles in the convoy (with $n \lt 1000$). The following lines each contain two positive integers $W$ and $S$ (separated by a space), where $W$ is the vehicle’s weight (in tons) and $S$ is its top speed for crossing the bridge (in kilometers per hour). The weights and speeds are given in the order the vehicles are queued.

Output a real number, rounded to 1 decimal place, representing the minimum total time for the entire convoy to cross the bridge (in minutes).

The testdata guarantees that all input numbers are within $[1, 10^{10}]$. Translated by ChatGPT 5