Background

"Happy birthday!!"

Little M received his girlfriend’s birthday wishes and a present.

Problem Description

Little M’s girlfriend gave Little M an $n \times n$ grid as a birthday present, and each cell of the grid contains a non-negative integer.

Unfortunately, some cells contain numbers that are too large. Little M does not like them, so he will place $k$ dominoes on the grid to cover those cells with numbers that are too large.

More precisely, Little M places the dominoes according to the following rules.

• Each domino is a $1 \times 2$ rectangle and cannot be split.
• Dominoes do not overlap (but they may touch).
• The sum of all visible (uncovered) cells must be as small as possible.

Your task is to determine the minimum possible sum of the numbers in the visible area. The testdata guarantees that it is possible to place $k$ dominoes without overlap.

Input Format

The first line contains two positive integers $n, k$, where $n$ is the size of the grid and $k$ is the number of dominoes.

The next $n$ lines each contain $n$ integers $a_i$. These $n \times n$ numbers describe Mirko’s grid.

Output Format

Output one integer: the minimum possible sum of the numbers in the visible area.

3 1
2 7 6
9 5 1
4 3 8

31

4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1

17

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^3$, $1 \le k \le 8$, and $0 \le a_i \le 10^3$.

Notes

Translated from COCI 2015-2016 #3 F DOMINO, full score 160.

Translated by ChatGPT 5