Ecology

The kingdom of Polyminogonia recently passed an ecological law that obligates every farm in the kingdom to preserve the maximum number of trees possible in a fixed percentage of the area of the farm. In addition, to allow wild animals to move freely, the preserved area must be connected. The farms in Polyminogonia are always a grid of N × N squares, one hectare each. The figure illustrates one farm, for N = 5. The preserved area should cover exactly M squares. In the example, M = 6. It should be orthogonally connected. That is, it must be possible to move between any two preserved squares making only orthogonal moves between preserved squares. The area not preserved may or may not be connected.

The farmers know the number of trees inside each square, and you have to write a program that computes the maximum number of trees that can be preserved with an area of M squares. In the example, it is possible to preserve 377 trees!