> > Congratulations to Jim Wilson for his Python solution to this year's
> > Codeslinger championship. Several of us hammered away with brute force
> > solutions, but Jim sliced through this problem with a quick and simple
> > approach based on "greedy" grouping. We continued trying for half an
> > hour after Jim submitted his solution, but still none of us could
> > solve the problem.
>
> For those who don't make it to the meetings, is the problem posted
> anywhere?...so we can take a whack at it before seeing the solution(s).
>

Convoy
A convoy of vehicles has lined up on a single lane and one-way street
in front of a single lane and one-way bridge over a river. Note that
since the street is single lane, no vehicle can overtake any other.
The bridge can sustain a given maximum load. To control the traffic on
the bridge, operators are stationed on either end of the bridge. The
convoy of vehicles is to be divided into groups, such that all the
vehicles in any group can cross the bridge together. When a group
reaches the other side, the operator on that side of the bridge uses a
telephone to inform the operator on this side that the next group can
start its journey over the bridge. The weight of each vehicle is
known. The sum of the weights of the vehicles in any group cannot
exceed the maximum load sustainable by the bridge. Associated with
each vehicle is the maximum speed with which it can travel over the
bridge. The time taken by a group of vehicles is calculated as the
time taken by the slowest vehicle in the group to cross the bridge.
The problem is to find the minimum amount of time in which the entire
convoy can cross the bridge.

Input to the Program
The first line of input contains three positive integers (separated by
blanks): the first one represents the maximum load that the bridge can
sustain (in tonnes); the second one represents the length of the
bridge (in kms); and the third one is the number of vehicles (n) in
the convoy. Each of the next n lines of input contains a pair of
positive integers, w s (separated by blanks), where w is the weight of
the vehicle (in tonnes) and s is the maximum speed (in kmph) with
which this vehicle can travel over the bridge. The weights and speeds
of the vehicles are specified in the same order as the order in which
the vehicles are queued up. You can assume that n < 1000.

Output of the Program
The output of the program should be a single real number specifying
the minimum time in minutes in which the convoy can cross the bridge.

=========
= Input file =
=========

100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70