**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

Problem 1: Dividing the Path [Hal Burch, 2004]

Farmer John's cows have discovered that the clover growing along
the ridge of the hill in his field is particularly good. To keep
the clover watered, Farmer John is installing water sprinklers along
the ridge of the hill.

To make installation easier, each sprinkler head must be installed
along the ridge of the hill (which we can think of as a one-dimensional
number line of length L (1 <= L <= 1,000,000); L is even).

Each sprinkler waters the ground along the ridge for some distance
in both directions. Each spray radius is an integer in the range A..B
(1 <= A <= B <= 1000). Farmer John needs to water the entire ridge in a
manner that covers each location on the ridge by exactly one sprinkler
head. Furthermore, FJ will not water past the end of the ridge in
either direction.

Each of Farmer John's N (1 <= N <= 1000) cows has a range of clover
that she particularly likes (these ranges might overlap). The ranges
are defined by a closed interval (S,E). Each of the cow's preferred
ranges must be watered by a single sprinkler, which might or might
not spray beyond the given range.

Find the minimum number of sprinklers required to water the entire
ridge without overlap.

PROBLEM NAME: divide

INPUT FORMAT:

* Line 1: Two space-separated integers: N and L

* Line 2: Two space-separated integers: A and B

* Lines 3..N+2: Each line contains two integers, S and E (0 <= S < E
        <= L) specifying the start end location respectively of a
        range preferred by some cow.  Locations are given as distance
        from the start of the ridge and so are in the range 0..L.

SAMPLE INPUT (file divide.in):

2 8
1 2
6 7
3 6

INPUT DETAILS:

Two cows along a ridge of length 8.  Sprinkler heads are available
in integer spray radii in the range 1..2 (i.e., 1 or 2).  One cow
likes the range 3-6, and the other likes the range 6-7.

OUTPUT FORMAT:

* Line 1: The minimum number of sprinklers required.  If it is not
        possible to design a sprinkler head configuration for Farmer
        John, output -1.

SAMPLE OUTPUT (file divide.out):

3

OUTPUT DETAILS:

Three sprinklers are required: one at 1 with spray distance 1, and
one at 4 with spray distance 2, and one at 7 with spray distance
1. The second sprinkler waters all the clover of the range like by
the second cow (3-6). The last sprinkler waters all the clover of
the range liked by the first cow (6-7). Here's a diagram:

                 |-----c2----|-c1|       cows' preferred ranges
     |---1---|-------2-------|---3---|   sprinklers
     +---+---+---+---+---+---+---+---+
     0   1   2   3   4   5   6   7   8

The sprinklers are not considered to be overlapping at 2 and 6.

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

Problem 2: Fence Obstacle Course [USACO coaches, 2004]

Farmer John has constructed an obstacle course for the cows'
enjoyment.  The course consists of a sequence of N fences (1 <= N
<= 50,000) of varying lengths, each parallel to the x axis. Fence
i's y coordinate is i.

The door to FJ's barn is at the origin (marked '*' below). The
starting point of the course lies at coordinate (S,N).

   +-S-+-+-+        (fence #N)
 +-+-+-+            (fence #N-1)
     ...               ...
   +-+-+-+          (fence #2)
     +-+-+-+        (fence #1)
=|=|=|=*=|=|=|      (barn)
-3-2-1 0 1 2 3    

FJ's original intention was for the cows to jump over the fences,
but cows are much more comfortable keeping all four hooves on the
ground. Thus, they will walk along the fence and, when the fence
ends, they will turn towards the x axis and continue walking in a
straight line until they hit another fence segment or the side of
the barn.  Then they decide to go left or right until they reach
the end of the fence segment, and so on, until they finally reach
the side of the barn and then, potentially after a short walk, the
ending point.

Naturally, the cows want to walk as little as possible. Find the
minimum distance the cows have to travel back and forth to get from
the starting point to the door of the barn.

PROBLEM NAME: obstacle

INPUT FORMAT:

* Line 1: Two space-separated integers: N and S (-100,000 <= S <=
        100,000)

* Lines 2..N+1: Each line contains two space-separated integers: A_i
        and B_i (-100,000 <= A_i < B_i <= 100,000), the starting and
        ending x-coordinates of fence segment i. Line 2 describes
        fence #1; line 3 describes fence #2; and so on. The starting
        position will satisfy A_N <= S <= B_N. Note that the fences
        will be traversed in reverse order of the input sequence.

SAMPLE INPUT (file obstacle.in):

4 0 
-2 1
-1 2
-3 0
-2 1

INPUT DETAILS:

Four segments like this:

   +-+-S-+             Fence 4
 +-+-+-+               Fence 3
     +-+-+-+           Fence 2
   +-+-+-+             Fence 1
 |=|=|=*=|=|=|         Barn
-3-2-1 0 1 2 3      

OUTPUT FORMAT:

* Line 1: The minimum distance back and forth in the x direction
        required to get from the starting point to the ending point by
        walking around the fences. The distance in the y direction is
        not counted, since it is always precisely N.

SAMPLE OUTPUT (file obstacle.out):

4

OUTPUT DETAILS:

Walk positive one unit (to 1,4), then head toward the barn, trivially
going around fence 3. Walk positive one more unit (to 2,2), then
walk to the side of the barn.  Walk two more units toward the origin
for a total of 4 units of back-and-forth walking.

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

Problem 3: Cow Ski Area [Adam Rosenfield, 2004]

Farmer John's cousin, Farmer Ron, who lives in the mountains of
Colorado, has recently taught his cows to ski.  Unfortunately, his
cows are somewhat timid and are afraid to ski among crowds of people
at the local resorts, so FR has decided to construct his own private
ski area behind his farm.

FR's ski area is a rectangle of width W and length L of 'land
squares' (1 <= W <= 500; 1 <= L <= 500).  Each land square is an
integral height H above sea level (0 <= H <= 9,999).  Cows can ski
horizontally and vertically between any two adjacent land squares,
but never diagonally.  Cows can ski from a higher square to a lower
square but not the other way and they can ski either direction
between two adjacent squares of the same height.

FR wants to build his ski area so that his cows can travel between
any two squares by a combination of skiing (as described above) and
ski lifts.  A ski lift can be built between any two squares of the
ski area, regardless of height. Ski lifts are bidirectional.  Ski
lifts can cross over each other since they can be built at varying
heights above the ground, and multiple ski lifts can begin or end
at the same square.  Since ski lifts are expensive to build, FR
wants to minimize the number of ski lifts he has to build to allow
his cows to travel between all squares of his ski area.

Find the minimum number of ski lifts required to ensure the cows
can travel from any square to any other square via a combination of
skiing and lifts.

TIME LIMIT: 0.4 seconds

PROBLEM NAME: skiarea

INPUT FORMAT:

* Line 1: Two space-separated integers: W and L

* Lines 2..L+1: L lines, each with W space-separated integers
        corresponding to the height of each square of land.

SAMPLE INPUT (file skiarea.in):

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

OUTPUT FORMAT:

* Line 1: A single integer equal to the minimal number of ski lifts FR
        needs to build to ensure that his cows can travel from any
        square to any other square via a combination of skiing and ski
        lifts

SAMPLE OUTPUT (file skiarea.out):

3

OUTPUT DETAILS:

FR builds the three lifts.  Using (1, 1) as the lower-left corner,
the lifts are (3, 1) <-> (8, 2), (7, 3) <-> (5, 2), and (1, 3) <->
(2, 2).  All locations are now connected.  For example, a cow wishing
to travel from (9, 1) to (2, 2) would ski (9, 1) -> (8, 1) -> (7,
1) -> (7, 2) -> (7, 3), take the lift from (7, 3) -> (5, 2), ski
(5, 2) -> (4, 2) -> (3, 2) -> (3, 3) -> (2, 3) -> (1, 3), and then
take the lift from (1, 3) - > (2, 2).  There is no solution using
fewer than three lifts.

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