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

Problem 1: Muddy Fields [Alex Schwendner, 2004]

Rain has pummeled the cows' field, a rectangular grid of R rows and
C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass,
the rain makes some patches of bare earth quite muddy. The
cows, being meticulous grazers, don't want to get their hooves dirty
while they eat.

To prevent those muddy hooves, Farmer John will place a number of
wooden boards over the muddy parts of the cows' field.  Each of the
boards is 1 unit wide, and can be any length long.  Each board must
be aligned parallel to one of the sides of the field.

Farmer John wishes to minimize the number of boards needed to cover
the muddy spots, some of which might require more than one board
to cover.  The boards may not cover any grass and deprive the cows
of grazing area but they can overlap each other.

Compute the minimum number of boards FJ requires to cover all the mud in
the field.

PROBLEM NAME: cover

INPUT FORMAT:

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Each line contains a string of C characters, with '*'
        representing a muddy patch, and '.' representing a grassy
        patch. No spaces are present.

SAMPLE INPUT (file cover.in):

4 4
*.*.
.***
***.
..*.

OUTPUT FORMAT:

* Line 1: A single integer representing the number of boards FJ needs.

SAMPLE OUTPUT (file cover.out):

4

OUTPUT DETAILS:

Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.

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

Problem 2: The Wedding Juicer [Maria Plachta, 1999]

Farmer John's cows have taken a side job designing interesting punch-bowl
designs. The designs are created as follows:

      * A flat board of size W cm x H cm is procured
        (3 <= W <= 300, 3 <= H <= 300)

      * On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm
        block is placed.  This block has some integer height B (1
        <= B <= 1,000,000,000)

The blocks are all glued together carefully so that punch will not drain
through them. They are glued so well, in fact, that the corner blocks
really don't matter!

FJ's cows can never figure out, however, just how much punch their bowl
designs will hold. Presuming the bowl is freestanding (i.e., no special
walls around the bowl), calculate how much juice the bowl can hold.  Some
juice bowls, of course, leak out all the juice on the edges and will hold 0.

PROBLEM NAME: juice

INPUT FORMAT:

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

* Lines 2..H+1: Line i+1 contains row i of bowl heights: W
        space-separated integers each of which represents the height B
        of a square in the bowl.  The first integer is the height of
        column 1, the second integers is the height of column 2, and
        so on.

SAMPLE INPUT (file juice.in):

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

OUTPUT FORMAT:

* Line 1: A single integer that is the number of cc's the described
        bowl will hold.

SAMPLE OUTPUT (file juice.out):

12

OUTPUT DETAILS:

Fill-up the two squares of height 1 to height 5, for 4 cc for each square.
 Fill the square of height 2 to height 5, for 3 cc of joice.  Fill the
square of height 6 to height 7 for 1 cc of juice.  2*4 + 3 + 1 = 12.

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

Problem 3: Naptime [Tiankai Liu, 2004]

Goneril is a very sleep-deprived cow. Her day is partitioned into
N (3 <= N <= 3,830) equal time periods but she can spend only B (2
<= B < N) not necessarily contiguous periods in bed.  Due to her
bovine hormone levels, each period has its own utility U_i (0 <=
U_i <= 200,000), which is the amount of rest derived from sleeping
during that period.  These utility values are fixed and are independent
of what Goneril chooses to do, including when she decides to be in
bed.

With the help of her alarm clock, she can choose exactly which
periods to spend in bed and which periods to spend doing more
critical items such as writing papers or watching baseball. However,
she can only get in or out of bed on the boundaries of a period.

She wants to choose her sleeping periods to maximize the sum of the
utilities over the periods during which she is in bed.  Unfortunately,
every time she climbs in bed, she has to spend the first period
falling asleep and gets no sleep utility from that period.

The periods wrap around in a circle; if Goneril spends both periods
N and 1 in bed, then she does get sleep utility out of period 1.

What is the maximum total sleep utility Goneril can achieve?

PROBLEM NAME: naptime

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer, U_i, between 0 and
        200,000 inclusive

SAMPLE INPUT (file naptime.in):

5 3
2
0
3
1
4

INPUT DETAILS:

The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that 
order. Goneril must pick 3 periods.

OUTPUT FORMAT:

* Line 1: A single integer, the maximum total sleep utility Goneril
        can achieve.

SAMPLE OUTPUT (file naptime.out):

6

OUTPUT DETAILS:

Goneril can get total utility 6 by being in bed during periods 4,
5, and 1, with utilities 0 [getting to sleep], 4, and 2
respectively.

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