Partitioning the Farm

Farmer John's farm is divided into an $N \times N$ square grid of pastures ($2 \le N \le 15$). Right now there is a fence only around the outside of the farm, so cows can move freely from pasture to pasture.

Farmer John has decided to build fences to separate the cows from one another. Because of zoning laws, each fence must be a horizontal or vertical line that runs all the way across the farm, and a fence cannot cut through a pasture (so every fence lies between two adjacent rows or between two adjacent columns). Farmer John can afford to build at most $K$ fences ($1 \le K \le 2N - 2$).

The size of a group is the total number of cows in it, and two cows belong to the same group if one can reach the other without crossing any fence. Farmer John wants to place the fences so as to minimize the size of the largest resulting group. Given the current number of cows in each pasture, compute the size of the largest group of cows when the fences are built optimally.

• Line 1: Two integers, $N$ and $K$.
• Lines 2 to $N+1$: Each line contains $N$ integers describing the number of cows in each pasture of one row of the farm (each pasture holds between $0$ and $1000$ cows).

• Line 1: The minimum possible size of the largest group of cows.

Explanation of the sample

Farmer John should build one fence between columns 2 and 3 and one fence between rows 2 and 3. This creates 4 groups of 4 cows each, so the largest group has size $4$.