**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Two problems numbered 1 through 2
**********************************************************************

Problem 1: Skiing [Brian Jacokes, 2002]

Bessie and the rest of Farmer John's cows are taking a trip this
winter to go skiing.  One day Bessie finds herself at the top left
corner of an R (1 <= R <= 100) by C (1 <= C <= 100) grid of elevations
E (-25 <= E <= 25). In order to join FJ and the other cows at a
discow party, she must get down to the bottom right corner as quickly
as she can by travelling only north, south, east, and west.

Bessie starts out travelling at a initial speed V (1 <= V <=
1,000,000).  She has discovered a remarkable relationship between
her speed and her elevation change.  When Bessie moves from a
location of height A to an adjacent location of height B, her speed
is multiplied by the number 2^(A-B).  The time it takes Bessie to
travel from a location to an adjacent location is the reciprocal
of her speed when she is at the first location.

Find the both smallest amount of time it will take Bessie to join
her cow friends and the number of moves required by the path (a
move is a transition from one location to another adjacent location).

PROBLEM NAME: cowski

INPUT FORMAT:

* Line 1: Three space-separated integers: V, R, and C, which
        respectively represent Bessie's initial velocity and the
        number of rows and columns in the grid.

* Lines 2..R+1: C integers representing the elevation E of the
        corresponding location on the grid.

SAMPLE INPUT (file cowski.in):

1 3 3
1 5 3
6 3 5
2 4 3

OUTPUT FORMAT:

A single number value, printed to two exactly decimal places: the
minimum amount of time that Bessie can take to reach the bottom right
corner of the grid.

SAMPLE OUTPUT (file cowski.out):

29.00

OUTPUT DETAILS:

Bessie's best route is:
	Start at 1,1 time  0 speed 1
	East  to 1,2 time  1 speed 1/16
	South to 2,2 time 17 speed 1/4
	South to 3,2 time 21 speed 1/8
	East  to 3,3 time 29 speed 1/4

**********************************************************************

Problem 2: Flying Right [Hal Burch, 2004]

Figuring that they cannot do worse than the humans have, Farmer
John's cows have decided to start an airline.  Being cows, they
decide to cater to the heretofore-untapped market of cows as
passengers. They plan to serve the cows who live along the western
coast of Lake Michigan. Each morning, they will fly from the
northern-most point of the coast southward towards Chicowgo, making
many stops along the way.  Each evening, they will fly back north
to the northern-most point.

They need your help to decide which passengers to carry each day.
Each of N (1 <= N <= 10,000) farms numbered 1..N along the coast
contains an airport (Farm 1 is northern-most; farm N is southern-most).
On this day, K (1 <= K <= 50,000) groups of cows wish to travel.
Each group of cows wants to fly from a particular farm to another
particular farm.  The airline, if it wishes, is allowed to stop and
pick up only part of a group. Cows that start a flight, however,
must stay on the plane until they reach their destination.

Given the capacity C (1 <= C <= 100) of the airplane and the groups
of cows that want to travel, determine the maximum number of cows
that the airline can fly to their destination.

PROBLEM NAME: flight

INPUT FORMAT:

* Line 1: Three space-separated integers: K, N, and C

* Lines 2..K+1: Each line contains three space-separated integers S,
        E, and M that specify a group of cows that wishes to travel. 
        The M (1 <= M <= C) cows are currently at farm S and want to
        travel to farm E (S != E).

SAMPLE INPUT (file flight.in):

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

INPUT DETAILS:

Four groups of cows, eight farms, and three seats on the
plane.

OUTPUT FORMAT:

* Line 1: The maximum number of cows that can be flown to their
        destination. This is the sum of the number of cows flown to
        their destination on the flight southward in the morning plus
        the number of cows flown to their destination on the flight
        northward in the evening.

SAMPLE OUTPUT (file flight.out):

6

OUTPUT DETAILS:

In the morning, the flight takes 2 cows from 1->3, 1 cow from 2->8,
and 1 cow from 4->7.  In the evening, the flight takes 2 cows from
8->3.

**********************************************************************