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

Problem 6: Yogurt factory [Tiankai Liu, 2004]

The cows have purchased a yogurt factory that makes world-famous
Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price
of milk and labor will fluctuate weekly such that it will cost the
company C_i (1 <= C_i <= 5,000) cents to produce one unit of yogurt
in week i.  Yucky's factory, being well-designed, can produce arbitrarily
many units of yogurt each week.

Yucky Yogurt owns a warehouse that can store unused yogurt at a
constant fee of S (1 <= S <= 100) cents per unit of yogurt per week.
Fortuitously, yogurt does not spoil.  Yucky Yogurt's warehouse is enormous,
so it can hold arbitrarily many units of yogurt.

Yucky wants to find a way to make weekly deliveries of Y_i (0 <=
Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery
quantity in week i). Help Yucky minimize its costs over the entire
N-week period. Yogurt produced in week i, as well as any yogurt
already in storage, can be used to meet Yucky's demand for that
week.

PROBLEM NAME: yogurt

INPUT FORMAT:

* Line 1: Two space-separated integers, N and S.

* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i
        and Y_i.

SAMPLE INPUT (file yogurt.in):

4 5
88 200
89 400
97 300
91 500

OUTPUT FORMAT:

* Line 1: Line 1 contains a single integer: the minimum total cost to
        satisfy the yogurt schedule.  Note that the total might be too
        large for a 32-bit integer.

SAMPLE OUTPUT (file yogurt.out):

126900

OUTPUT DETAILS:

In week 1, produce 200 units of yogurt and deliver all of it. In
week 2, produce 700 units: deliver 400 units while storing 300
units. In week 3, deliver the 300 units that were stored. In week
4, produce and deliver 500 units.

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

Problem 7: Checking an Alibi [Hal Burch, 2004]

A crime has been comitted: a load of grain has been taken from the barn by
one of FJ's cows.  FJ is trying to determine which of his C (1 <= C <=
100) cows is the culprit.  Fortunately, a passing satellite took an image
of his farm M (1 <= M <= 70000) seconds before the crime took place, giving
the location of all of the cows.  He wants to know which cows had time to
get to the barn to steal the grain.

Farmer John's farm comprises F (1 <= F <= 500) fields numbered 1..F
and connected by P (1 <= P <= 1,000) bidirectional paths whose
traversal time is in the range 1..70000 seconds (cows walk very
slowly).  Field 1 contains
the barn.  It takes no time to travel within a field (switch paths).

Given the layout of Farmer John's farm and the location of each cow
when the satellite flew over, determine set of cows who could be
guilty.

NOTE: Do not declare a variable named exactly 'time'. This will reference
the system call and never give you the results you really want.

PROBLEM NAME: alibi

INPUT FORMAT:

* Line 1: Four space-separated integers: F, P, C, and M

* Lines 2..P+1: Three space-separated integers describing a path: F1,
        F2, and T. The path connects F1 and F2 and requires T seconds
        to traverse.

* Lines P+2..P+C+1: One integer per line, the location of a cow.  The
        first line gives the field number of cow 1, the second of cow
        2, etc.

SAMPLE INPUT (file alibi.in):

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

INPUT DETAILS:

Fields/distances like this:
          6
      4------5
      |      |
     2|      |
      |      |
7-----1      |5
   9  |      |
     1|      |
      |      |
      2------3
          6

OUTPUT FORMAT:

* Line 1: A single integer N, the number of cows that could be guilty
        of the crime.

* Lines 2..N+1: A single cow number on each line that is one of the
        cows that could be guilty of the crime. The list must be in
        ascending order.

SAMPLE OUTPUT (file alibi.out):

4
1
2
3
4

OUTPUT DETAILS:

Any cow except cow 5 could have done it.  Cow 5 would take 9 seconds to get
to the barn.

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

Problem 8: Out of Hay [Coaches, 2004]

The cows have run out of hay, a horrible event that must be remedied
immediately. Bessie intends to visit the other farms to survey their
hay situation. There are N (2 <= N <= 2,000) farms (numbered 1..N);
Bessie starts at Farm 1.  She'll traverse some or all of the M (1
<= M <= 10,000) two-way roads whose length does not exceed 1,000,000,000
that connect the farms. Some farms may be multiply connected with
different length roads. All farms are connected one way or another
to Farm 1.

Bessie is trying to decide how large a waterskin she will need.  She knows
that she needs one ounce of water for each unit of length of a road. Since
she can get more water at each farm, she's only concerned about the length
of the longest road. Of course, she plans her route between farms such that
she minimizes the amount of water she must carry.

Help Bessie know the largest amount of water she will ever have to
carry: what is the length of longest road she'll have to travel
between any two farms, presuming she chooses routes that minimize
that number? This means, of course, that she might backtrack over
a road in order to minimize the length of the longest road she'll have
to traverse.

PROBLEM NAME: outofhay

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M.

* Lines 2..1+M: Line i+1 contains three space-separated integers, A_i,
        B_i, and L_i, describing a road from A_i to B_i of length L_i.

SAMPLE INPUT (file outofhay.in):

3 3
1 2 23
2 3 1000
1 3 43

OUTPUT FORMAT:

* Line 1: A single integer that is the length of the longest road
        required to be traversed.

SAMPLE OUTPUT (file outofhay.out):

43

OUTPUT DETAILS:

In order to reach farm 2, Bessie travels along a road of length 23.
To reach farm 3, Bessie travels along a road of length 43.  With
capacity 43, she can travel along these roads provided that she
refills her tank to maximum capacity before she starts down a road.

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