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

Problem 1: Building A New Barn [Jeffrey Wang, 2007]

After scrimping and saving for years, Farmer John has decided to
build a new barn. He wants the barn to be highly accessible, and
he knows the coordinates of the grazing spots of all N (2 <= N <=
10,000) cows. Each grazing spot is at a point with integer coordinates
(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000).
The hungry cows never graze in spots that are horizontally or
vertically adjacent.

The barn must be placed at integer coordinates and cannot be on any
cow's grazing spot. The inconvenience of the barn for any cow is
given the Manhattan distance formula |X-X_i|+|Y-Y_i|, where (X, Y)
and (X_i, Y_i) are the coordinates of the barn and the cow's grazing
spot, respectively.  Where should the barn be constructed in order
to minimize the sum of its inconvenience for all the cows?

PROBLEM NAME: newbarn

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers which
        are the grazing location (X_i, Y_i) of cow i

SAMPLE INPUT (file newbarn.in):

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

INPUT DETAILS:

The field contains 4 cows with grazing spots at the points (1, -3),
(0, 1), (-2, 1), and (1, -1).

OUTPUT FORMAT:

* Line 1: Two space-separated integers: the minimum inconvenience for
        the barn and the number of spots on which Farmer John can
        build the barn to achieve this minimum.

SAMPLE OUTPUT (file newbarn.out):

10 4

OUTPUT DETAILS:

The minimum inconvenience is 10, and there are 4 spots that Farmer John can
build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).

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

Problem 2: Cow Sorting [Osman Ay, 2004]

Farmer John's N (1 <= N <= 10,000) cows are lined up to be milked
in the evening.  Each cow has a unique "grumpiness" level in the range
1...100,000.  Since grumpy cows are more likely to damage FJ's milking
equipment, FJ would like to reorder the cows in line so they are lined up
in increasing order of grumpiness.  During this process, the places of any
two cows (not necessarily adjacent) can be interchanged.  Since grumpy cows
are harder to move, it takes FJ a total of X+Y units of time to exchange
two cows whose grumpiness levels are X and Y.

Please help FJ calculate the minimal time required to reorder the cows.

PROBLEM NAME: csort

INPUT FORMAT:

* Line 1: A single integer: N.

* Lines 2..N+1: Each line contains a single integer: line i+1
        describes the grumpiness of cow i.

SAMPLE INPUT (file csort.in):

3
2
3
1

INPUT DETAILS:

Three cows are standing in line with respective grumpiness levels 2, 3, and 1.

OUTPUT FORMAT:

* Line 1: A single line with the minimal time required to reorder the
        cows in increasing order of grumpiness.

SAMPLE OUTPUT (file csort.out):

7

OUTPUT DETAILS:

2 3 1 : Initial order.   
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4). 
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3). 

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

Problem 3: Lilypad Pond [Richard Ho, 2006]

FJ has installed a beautiful pond for his cows' aesthetic 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 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 already intrude on a cell.

Help Farmer John determine the minimum number of additional lilypads
he has to place, and in how many ways he can place that minimum
number.

PROBLEM NAME: lilypad

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 lilypad.in):

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0

INPUT DETAILS:

The ponds has 4 rows and 5 columns. Bessie is at row 2 column 1, and she
wants to reach row 4 column 4. A rock and three 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 total number of possible ways the
        additional lilypads can be positioned.  This number is
        guaranteed to fit into a single 64-bit signed integer. Do not
        output this line if line 1 contains -1.

SAMPLE OUTPUT (file lilypad.out):

2
3

OUTPUT DETAILS:

Two lilypads are required. There are three ways to place them: row
4 column 2 and row 2 column 3; row 1 column 3 and row 3 column 2;
or row 1 column 3 and row 2 column 5:

          R1C2,R2C3     R1C3,R3C2     R1C3,R2C5
          1 0 0 0 0     1 0 X 0 0     1 0 X 0 0
          3 0 X 0 0     3 0 0 0 0     3 0 0 0 X
          0 0 2 0 0     0 X 2 0 0     0 0 2 0 0
          0 X 0 4 0     0 0 0 4 0     0 0 0 4 0

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