The Optimal Fence Partitioning Problem

Farmer John's farm is represented as an \(N\times N\) grid (with \(2 \le N \le 15\)). Each cell contains a certain number of cows. Initially, there is a fence surrounding the whole farm, so cows may move anywhere inside. Farmer John now plans to install up to \(K\) new fences (with \(1 \le K \le 2N-2\)) in order to separate the cows. Each new fence is a full horizontal or vertical line drawn between the rows or columns (i.e. fences cannot cut through a cell).

After installing fences, the farm is divided into several connected regions (two pastures are in the same region if they can reach each other without crossing a fence). Let \(S\) denote the sum of cows in a region. Farmer John’s goal is to minimize the maximum \(S\) over all regions. In other words, he wants to choose the positions of up to \(K\) fences such that if \(M\) is the maximum regional sum after partitioning, \(M\) is as small as possible.

Input Example: Given an \(n\times n\) matrix where each entry denotes the number of cows in that pasture, and an integer \(K\) representing the maximum number of fences.

Task: Compute the minimal possible value of the maximum region sum after placing the fences optimally.

Hint: You may use a binary search approach combined with enumerating possible vertical fence placements (there are \(N-1\) possible vertical positions) and a greedy strategy to decide where horizontal fences must be placed.

inputFormat

The first line contains two integers \(N\) and \(K\) separated by a space. \(N\) is the size of the grid and \(K\) is the maximum number of additional fences. Following this, there are \(N\) lines, each containing \(N\) space‐separated integers. The \(j\)-th integer in the \(i\)-th line denotes the number of cows in the pasture at row \(i\) and column \(j\).

Constraints: \(2 \le N \le 15\) and \(1 \le K \le 2N-2\).

Example:

2 1
2 2
2 2

This represents a 2x2 grid with each cell having 2 cows and you may install at most 1 fence.

outputFormat

Output a single integer: the minimum possible value of the maximum regional cow sum when fences are optimally placed.

Example (corresponding to the above input):

4

Explanation: One optimal strategy is to place a vertical fence between the columns, which partitions the grid into two regions, each with a total of 4 cows.

sample

2 1
2 2
2 2

4

</p>