Deforestation   notree.X

The cows are visiting Farmer Ran's cousin (Farmer Melissa) in Plovdiv,
Bulgaria. Farmer Melissa's pasture, however, is covered with beautiful
oak trees that she wishes to harvest.

Farmer Melissa has placed irresistible cow-treats at K (2 <= K <= 10)
unforested grid squares in his mostly dense forest which is represented
by a grid with R (1 <= R <= 10) rows and C (1 <= C <= 10) columns.
FM has also tabulated the cost C_ij (1 <= C_ij <= 100,000) to clear
each of the remaining grid squares. C_ij == 0 when a square contains
a treat.

Farmer Ran, back in Wisconsin, is hiring a Sikorsky helicopter to
drop the cows on a square of their choosing in the Bulgarian forest.
The cows must clear various grids the forest as they make their way
rectilinearly from treat to treat, ultimately consuming all the
cow-treats.

Of course, the cows wish to spend as little as possible to clear
the forest enough to obtain all their treats. What is the minimum
cost?

PROBLEM NAME: notree

INPUT FORMAT:

* Line 1: Two integers: R and C

* Lines 2..R+1: Line i+1 contains C integers representing row i of the
        cost grid

SAMPLE INPUT:

4 5
0 1 1 0 9
2 5 5 1 33
1 5 5 1 10
0 1 1 0 99

OUTPUT FORMAT:

* Line 1: A single integer which is the minimum cost to clear the
        forest grids while collecting all the treats

SAMPLE OUTPUT:

6

OUTPUT DETAILS:

One solution is to start in the upper left corner (1,1) and proceed
right to the treat, down to the treat, and then left to the treat
while clearing the forest at costs of 1 unit per square.