Minimizing Visible Sum by Placing Dominoes

Little M received an \(n \times n\) grid as a birthday gift from his girlfriend. Each cell of the grid contains a non‑negative integer. Unfortunately, some cells have numbers that are too large for Little M's taste. To hide these undesirable numbers, he covers some cells with dominoes.

A domino is a \(1\times2\) rectangle and cannot be split. Dominoes must be placed so that:

• They cover two adjacent cells (either horizontally or vertically);
• They do not overlap (though they may touch);
• Exactly \(k\) dominoes are used;
• The sum of the numbers in the uncovered cells is minimized.

Since the total sum of all numbers is fixed, this is equivalent to selecting \(k\) disjoint domino placements with the maximum total sum. Note that because the grid is bipartite (like a chessboard), every domino covers one white and one black cell.

Your task is to compute the minimum possible sum of the visible (uncovered) numbers after placing exactly \(k\) dominoes. It is guaranteed that a placement of \(k\) dominoes exists.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq \text{constraints}\), \(1 \leq k \leq \text{number of domino placements}\)).

Each of the next \(n\) lines contains \(n\) non‑negative integers representing the grid.

It is guaranteed that it is possible to place exactly \(k\) dominoes without overlapping.

outputFormat

Output a single integer — the minimum sum of the numbers in the uncovered cells after placing \(k\) dominoes optimally.

sample

2 1
1 2
3 4

3