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

Problem 6: The Cow Lexicon [Vladimir Novakovski, 2002]

Few know that the cows have their own dictionary with W (1 <= W <=
600) words, each containing no more 25 of the characters 'a'..'z'.
Their cowmunication system, based on mooing, is not very accurate;
sometimes they hear words that do not make any sense. For instance,
Bessie once received a message that said "browndcodw". As it turns
out, the intended message was "browncow" and the two letter "d"s
were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also
containing only characters in the range 'a'..'z') of length L (2
<= L <= 300) characters that is a bit garbled. In particular, they
know that the message has some extra letters, and they want you to
determine the smallest number of letters that must be removed to
make the message a sequence of words from the dictionary.

PROBLEM NAME: lexicon

INPUT FORMAT:

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

* Line 2: L characters (followed by a newline, of course): the
        received message

* Lines 3..W+2: The cows' dictionary, one word per line

SAMPLE INPUT (file lexicon.in):

6 10
browndcodw
cow
milk
white
black
brown
farmer


OUTPUT FORMAT:

* Line 1: a single integer that is the smallest number of characters
        that need to be removed to make the message a sequence of
        dictionary words.

SAMPLE OUTPUT (file lexicon.out):

2

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

Problem 7: Silver Lilypad Pond [Richard Ho, 2006]

FJ has installed a beautiful pond for his cows' esthetic enjoyment
and exercise. The rectangular pond has been partitioned into square
cells of M rows and N columns (1 <= M <= 30; 1 <= N <= 30). Some
of the cells have astonishingly sturdy lilypads; others have rocks;
the remainder are just beautiful, cool, blue water.

Bessie is practicing her ballet moves by jumping from one lilypad
to another and is currently located at one of the lilypads. She
wants to travel to another lilypad in the pond by jumping from one
lilypad to another.

Surprising only to the uninitiated, Bessie's jumps between lilypads
always appear as a chess-knight's move: one move in one direction
and then two more in the orthogonal direction (or perhaps two in
one direction and then one in the orthogonal direction).

Farmer John is observing Bessie's ballet drill and realizes that
sometimes she might not be able to jump to her destination lilypad
because intermediary lilypads are missing.

Ever thrifty, he wants to place a minimum of additional lilypads
so she can complete her quest (perhaps quickly; perhaps by using a
large number of intermediate lilypads). Of course, lilypads cannot
be placed where rocks are present.

Help Farmer John determine the minimum number of additional lilypads
he has to place. Also determine the minimum number of jumps required
to reach the destination when placing that minimum number of
additional lilypads in some optimal location. Finally, determine
the total number of unique ways Bessie can jump from the start to
the end in the minimum number of jumps (after the smallest number
of lily pads is placed in locations as needed, of course). The final
number includes jumps using any of the possible ways the new lilypads
are placed!

PROBLEM NAME: silvlily

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 describes row i of the pond using N
        space-separated integers with these values: 0 indicates empty
        water; 1 indicates a lilypad in place; 2 indicates rock in
        place; 3 indicates the lilypad Bessie starts on; 4 indicates
        the lilypad Bessie wants to travel to.

SAMPLE INPUT (file silvlily.in):

4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0

INPUT DETAILS:

The ponds has 4 rows and 8 columns. Bessie is at row 4 column 1, and she
wants to reach row 3 column 6. A rock and five lilypads are present.

OUTPUT FORMAT:

* Line 1: One integer: the minimum number of additional lilypads
        required. If it is not possible to help Bessie jump to her
        destination, print -1.

* Line 2: One integer: the minimum number of jumps Bessie must make
        when placing the minimum number of additional lilypads. Do not
        output this line if line 1 contains -1.

* Line 3: One integer: the number of paths from start to end that uses
        the minimum number of additional pads and the minimum number
        of jumps calculated in line 2. Do not output this line if line
        1 contains -1.

SAMPLE OUTPUT (file silvlily.out):

2
6
2

OUTPUT DETAILS:

Two lilypads are required as shown by the x's in each of the two
instances below:

    0 0 0 1 0 0 0 0     0 0 0 1 0 0 0 0
    0 x 0 0 0 2 0 1     0 0 0 0 0 2 0 1
    0 0 0 0 x 4 0 0     0 0 x 0 x 4 0 0
    3 0 0 0 0 0 1 0     3 0 0 0 0 0 1 0

Bessie must make at least 6 jumps to reach destination and there
are two different paths of 6 jumps as shown below.

    0 0 0 C 0 0 0 0     0 0 0 C 0 0 0 0
    0 B 0 0 0 2 0 F     0 0 0 0 0 2 0 F
    0 0 0 0 D G 0 0     0 0 B 0 D G 0 0
    A 0 0 0 0 0 E 0     A 0 0 0 0 0 E 0

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

Problem 8: Silver Cow Party [Richard Ho, 2006]

One cow from each of N farms (1 <= N <= 1000) conveniently numbered
1..N is going to attend the big cow party to be held at farm #X (1
<= X <= N). A total of M (1 <= M <= 100,000) unidirectional (one-way)
roads connects pairs of farms; road i requires Ti (1 <= Ti <= 100)
units of time to traverse.

Each cow must walk to the party and, when the party is over, return
to her farm. Each cow is lazy and thus picks an optimal route with
the shortest time. A cow's return route might be different from her
original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend
walking to the party and back?

PROBLEM NAME: sparty

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 describes road i with three space-separated
        integers: Ai, Bi, and Ti. The described road runs from farm Ai
        to farm Bi, requiring Ti time units to traverse.

SAMPLE INPUT (file sparty.in):

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

INPUT DETAILS:

Four cows; eight roads; party at farm 2.

OUTPUT FORMAT:

* Line 1: One integer: the maximum of time any one cow must walk.

SAMPLE OUTPUT (file sparty.out):

10

OUTPUT DETAILS:

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and
3 (7 units), for a total of 10 time units.

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