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

Problem 1: Cheapest Palindrome [Eko Mirhard, 2007]

Keeping track of all the cows can be a tricky task so Farmer John
has installed a system to automate it. He has installed on each cow
an electronic ID tag that the system will read as the cows pass by
a scanner. Each ID tag's contents are currently a single string
with length M (1 <= M <= 2,000) characters drawn from an alphabet
of N (1 <= N <= 26) different symbols (namely, the lower-case roman
alphabet).

Cows, being the mischievous creatures they are, sometimes try to
spoof the system by walking backwards. While a cow whose ID is
"abcba" would read the same no matter which direction the she walks,
a cow with the ID "abcb" can potentially register as two different
IDs ("abcb" and "bcba").

FJ would like to change the cows's ID tags so they read the same
no matter which direction the cow walks by. For example, "abcb" can
be changed by adding "a" at the end to form "abcba" so that the ID
is palindromic (reads the same forwards and backwards). Some other
ways to change the ID to be palindromic are include adding the three
letters "bcb" to the begining to yield the ID "bcbabcb" or removing
the letter "a" to yield the ID "bcb". One can add or remove characters
at any location in the string yielding a string longer or shorter
than the original string.

Unfortunately as the ID tags are electronic, each character insertion
or deletion has a cost (0 <= cost <= 10,000) which varies depending
on exactly which character value to be added or deleted. Given the
content of a cow's ID tag and the cost of inserting or deleting
each of the alphabet's characters, find the minimum cost to change
the ID tag so it satisfies FJ's requirements. An empty ID tag is
considered to satisfy the requirements of reading the same forward
and backward. Only letters with associated costs can be added to a
string.

PROBLEM NAME: cheappal

INPUT FORMAT:

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

* Line 2: This line contains exactly M characters which constitute the
       initial ID string

* Lines 3..N+2: Each line contains three space-separated entities: a
       character of the input alphabet and two integers which are
       respectively the cost of adding and deleting that character.

SAMPLE INPUT (file cheappal.in):

3 4
abcb
a 1000 1100
b 350 700
c 200 800

INPUT DETAILS:

The nametag is "abcb" with these per-operation costs:
 Insert Delete
a  1000   1100
b   350    700
c   200    800

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the minimum cost
       to change the given name tag.

SAMPLE OUTPUT (file cheappal.out):

900

OUTPUT DETAILS:

If we insert an "a" on the end to get "abcba", the cost would be
1000. If we delete the "a" on the beginning to get "bcb", the cost
would be 1100. If we insert "bcb" at the begining of the string, the
cost would be 350+200+350=900, which is the minimum.

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

Problem 2: Dining [Joe Zimmerman and Eric Price, 2006]

Cows are such finicky eaters. Each cow has a preference for certain
foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot
to check his menu against their preferences. Although he might not
be able to stuff everybody, he wants to give a complete meal of
both food and drink to as many cows as possible.

Farmer John has cooked F (1 <= F <= 100) types of foods and prepared
D (1 <= D <= 100) types of drinks. Each of his N (1 <= N <= 100)
cows has decided whether she is willing to eat a particular food
or drink a particular drink. Farmer John must assign a food type
and a drink type to each cow to maximize the number of cows who get
both.

Each dish or drink can only be consumed by one cow (i.e., once food
type 2 is assigned to a cow, no other cow can be assigned food type
2).

PROBLEM NAME: dining

INPUT FORMAT:

* Line 1: Three space-separated integers: N, F, and D

* Lines 2..N+1: Each line i starts with a two integers F_i and D_i,
       the number of dishes that cow i likes and the number of drinks
       that cow i likes. The next F_i integers  denote the dishes
       that cow i will eat, and the D_i integers following that
       denote the drinks that cow i will drink.

SAMPLE INPUT (file dining.in):

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

INPUT DETAILS:

Cow 1:  foods from {1,2}, drinks from {1,3}
Cow 2:  foods from {2,3}, drinks from {1,2}
Cow 3:  foods from {1,3}, drinks from {1,2}
Cow 4:  foods from {1,3}, drinks from {3}

OUTPUT FORMAT:

* Line 1: A single integer that is the maximum number of cows that can
       be fed both food and drink that conform to their wishes

SAMPLE OUTPUT (file dining.out):

3

OUTPUT DETAILS:

One way to satisfy three cows is:
Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3
The pigeon-hole principle tells us we can do no better since there are only
three kinds of food or drink. Other test data sets are more challenging, of
course.

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

Problem 3: Connect [Richard Peng, 2007]

It's a fairly well-known fact that Canada has two seasons: winter
and road construction. In the good old days before global warming,
road construction season was July while winter was the other 11
months. As the earth got warmer, road construction season now runs
April through September.

This is bad news for all the moose who use the road network as their
main method of transportation since their road usage is now disrupted
by road construction for six months rather than one. Canmuu The
Canadian Moose wants to build a travel scheduling system that knows
the status of all roads and can tell moose whether they could
possibly travel between cities by only taking the roads. Being a
bit dimwitted, moose will travel only roads that fall inclusively
in the range of columns bounded by the starting and ending cities.

Canmuu has noticed that all of the important road junctions (usually
cities) in Canada can be described as a grid and furthermore all
the roads connect neighboring points -- and only neighboring points
-- in the grid. He has drawn a rectilinear grid of R (1 <= R <= 2)
rows and C (1 <= C <= 15,000) columns where every point on the grid
represents a road junction. The following is an example of such a
grid for Southern Ontario (the *'s represent unconnected, empty
locations, i.e., farms):

   *      Orangeville---Barrie------Peterborough        *
                          |              |
Waterloo--Mississauga---Toronto--------Lindsey-------Kingston

In this example, although a path exists between Waterloo and
Orangeville, no acceptable path exists as the moose must go through
Toronto. If the road between Lindsey and Kingston is closed down,
it's no longer possible to travel from Waterloo to Kingston (or
from anywhere to Kingston). But if the road from Toronto to Lindsey
is closed down instead, it is still be possible to travel from
Waterloo to Kingston.

For easy reference, cities are denoted as row,column so the map
above becomes:

 1,1      1,2------1,3------1,4      1,5
                    |        |
 2,1------2,2------2,3------2,4------2,5

Canmuu has created a network that supplies real-time instructions
to a Moose Travel Scheduler. He even designed a system to inform
the scheduler of the N roads that already exist; they are in the
input file (see the description below).

The real-time instructions appear as single lines of input on the
'standard input' device, often known as the 'console'. Each line
has one of the formats below:

C r1 c1 r2 c2  The road connecting adjacent points r1,c1 to r2,c2
              is closed for maintenance.

O r1 c1 r2 c2  The road between adjacent points r1,c1 and r2,c2 is
              now open. This could either mean either a new road
              has been constructed or road maintenance on an
              existing road has been finished.

T r1 c1 r2 c2  A moose wants to travel only on roads from potentially
              non-adjacent points r1,c1 to r2,c2 using a path that
              does not go outside columns c1 and c2: reply with Y
              if he can; reply with N if he cannot.

E              No more requests are forthcoming; the scheduler
              program should exit.

Implement a program to read the initial road network and calculate
the answers to as many as 50,000 requests as they appear.

Your scheduling program will conduct a dialog with the 'reactive'
grading program:

   * Read lines in the format described above (there is no need
     to acknowledge 'C' or 'O' requests)

   * Print a single character on a line by itself to standard
     output when requested to do so by the 'T' directive

   * Exit your program after reading the 'E' line

Interactive programs usually require extra code that causes output
to be unbuffered -- to be written in real time instead of buffering
for faster (but later) output.

Those C/C++ users who use #include <stdio.h> should execute this
line before any input or output:

   setlinebuf (stdout);

Users of <stdio.h> should also use fgets () to read from stdin.
Use of scanf is not recommended; do something like this to parse
input data:

   char line[1000];
   setlinebuf (stdout);

   fgets (line, 1000, stdin);
   sscanf ("..format..", &var1, ...);

Those C++ users who use iostream should cout << flush after each
line (and also use cin in the normal manner):

   cout << answer << endl;
   cout << flush;

Java users should use the following output scheme for output:

   import java.io.*;
   ...
   PrintStream out = new PrintStream (System.out, true); // 'unbuffers' output
   ...
   out.println (answer);

For Pascal, add the following statement after each writeln statement:

flush(stdout);

Here's a sample dialog for the map above. The lines with "<-" are
lines that are data going to your program; lines with "->" are
output from you program to standard output (the console). Of course,
the little arrows do not appear in the actual input file; neither
does the explanatory text.

<- C 2 4 2 5        <-- The road connecting 2,4 and 2,5 is closed
<- T 2 1 2 5        <-- A moose wishes to travel from 2,1 to 2,5
-> N                <-- But that's not possible with the roads as they stand
<- T 2 1 1 2        <-- A moose wishes to travel from 2,1 to 1,2
-> N                <-- There is a path, but it's unacceptable in moose terms
<- C 2 3 2 4        <-- The road connecting 2,3 and 2,4 is closed
<- O 2 4 2 5        <-- The road connecting 2,4 and 2,5 is now open
<- T 2 1 2 5        <-- A moose wishes to travel from 2,1 to 2,5
-> Y                <-- Which is possible
<- E                <-- time to exit

Time limit for each test case:  1.60 CPU seconds

PROBLEM NAME: connect

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes a road in place using four
       space-separated integers which are respectively the row,column
       coordinates of two connected cities: r1, c1, r2, and c2. There
       are no duplicates in this list.

SAMPLE INPUT (file connect.in):

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

INPUT DETAILS:

Same as the road map described in the problem

OUTPUT FORMAT:

No lines are written to the output file.

SAMPLE OUTPUT (file connect.out):

[empty file]

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