**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Cow Picnic [Alex Schwendner, 2006]

The cows are having a picnic! Each of Farmer John's K (1 <= K <=
100) cows is grazing in one of N (1 <= N <= 1,000) pastures,
conveniently numbered 1...N. The pastures are connected by M (1 <=
M <= 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but
(because of the one-way paths) some cows may only be able to get
to some pastures. Help the cows out by figuring out how many pastures
are reachable by all cows, and hence are possible picnic locations.

PROBLEM NAME: picnic

INPUT FORMAT:

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

* Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the
        number of the pasture in which cow i is grazing.

* Lines K+2..M+K+1: Each line contains two space-separated integers,
        respectively A and B (both 1..N and A != B), representing a
        one-way path from pasture A to pasture B.

SAMPLE INPUT (file picnic.in):

2 4 4
2
3
1 2
1 4
2 3
3 4


INPUT DETAILS:

4<--3
^   ^
|   |
|   |
1-->2

The pastures are laid out as shown above, with cows in pastures 2 and 3.

OUTPUT FORMAT:

* Line 1: The single integer that is the number of pastures that are
        reachable by all cows via the one-way paths.

SAMPLE OUTPUT (file picnic.out):

2

OUTPUT DETAILS:

The cows can meet in pastures 3 or 4.

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

Problem 7: Cow Roller Coaster [Alex Schwendner, 2006]

The cows are building a roller coaster! They want your help to
design as fun a roller coaster as possible, while keeping to the
budget.

The roller coaster will be built on a long linear stretch of land
of length L (1 <= L <= 1,000). The roller coaster comprises a
collection of some of the N (1 <= N <= 10,000) different interchangable
components. Each component i has a fixed length Wi (1 <= Wi <= L).
Due to varying terrain, each component i can be only built starting
at location Xi (0 <= Xi <= L-Wi). The cows want to string together
various roller coaster components starting at 0 and ending at L so
that the end of each component (except the last) is the start of
the next component.

Each component i has a "fun rating" Fi (1 <= Fi <= 1,000,000) and
a cost Ci (1 <= Ci <= 1000). The total fun of the roller coster is
the sum of the fun from each component used; the total cost is
likewise the sum of the costs of each component used. The cows'
total budget is B (1 <= B <= 1000). Help the cows determine the
most fun roller coaster that they can build with their budget.

PROBLEM NAME: coaster

INPUT FORMAT:

* Line 1: Three space-separated integers: L, N and B.

* Lines 2..N+1: Line i+1 contains four space-separated integers,
        respectively: Xi, Wi, Fi, and Ci.

SAMPLE INPUT (file coaster.in):

5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2


OUTPUT FORMAT:

* Line 1: A single integer that is the maximum fun value that a
        roller-coaster can have while staying within the budget and
        meeting all the other constraints. If it is not possible to
        build a roller-coaster within budget, output -1.

SAMPLE OUTPUT (file coaster.out):

17

OUTPUT DETAILS:

Taking the 3rd, 5th and 6th components gives a connected roller-coaster
with fun value 17 and cost 7. Taking the first two components would
give a more fun roller-coaster (25) but would be over budget.

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

Problem 8: River Hopscotch [Richard Ho, 2006]

Every year the cows hold an event featuring a peculiar version of
hopscotch that involves carefully jumping from rock to rock in a
river. The excitement takes place on a long, straight river with a
rock at the start and another rock at the end, L units away from
the start (1 <= L <= 1,000,000,000). Along the river between the
starting and ending rocks, N (0 <= N <= 50,000) more rocks appear,
each at an integral distance Di from the start (0 < Di < L).

To play the game, each cow in turn starts at the starting rock and
tries to reach the finish at the ending rock, jumping only from
rock to rock. Of course, less agile cows never make it to the final
rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year.
But as time goes by, he tires of watching the timid cows of the
other farmers limp across the short distances between rocks placed
too closely together. He plans to remove several rocks in order to
increase the shortest distance a cow will have to jump to reach the
end. He knows he cannot remove the starting and ending rocks, but
he calculates that he has enough resources to remove up to M rocks
(0 <= M <= N).

FJ wants to know exactly how much he can increase the shortest
distance *before* he starts removing the rocks. Help Farmer John
determine the greatest possible shortest distance a cow has to jump
after removing the optimal set of M rocks.

PROBLEM NAME: jump

INPUT FORMAT:

* Line 1: Three space-separated integers: L, N, and M

* Lines 2..N+1: Each line contains a single integer indicating how far
        some rock is away from the starting rock. No two rocks share
        the same position.

SAMPLE INPUT (file jump.in):

25 5 2
2
14
11
21
17


INPUT DETAILS:

5 rocks at distances 2, 11, 14, 17, and 21. Starting rock at position
0, finishing rock at position 25.

OUTPUT FORMAT:

* Line 1: A single integer that is the maximum of the shortest
        distance a cow has to jump after removing M rocks

SAMPLE OUTPUT (file jump.out):

4

OUTPUT DETAILS:

Before removing any rocks, the shortest jump was a jump of 2 from
0 (the start) to 2. After removing the rocks at 2 and 14, the
shortest required jump is a jump of 4 (from 17 to 21 or from 21 to
25).

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