Namuk's Rotten Egg Tray

Time limit4sMemory limit512 MB

Summary

Place up to K nonoverlapping domino covers on an N by N tray to hide the most rottenness and report the remaining sum.

Level: Medium7 of 10
Topics: Backtracking, Sorting, Matrix
Solved: No attempts yet

Problem

Namuk sells eggs in an $N \times N$ egg tray. Every egg carries a rottenness value, and a larger value means a more rotten egg. While Namuk was busy with a new romance the eggs sat untouched and went bad, so he wants to hide the rotten ones under covers and bring the visible rottenness down.

The covers follow these rules.

One cover hides two eggs that sit next to each other horizontally or vertically.
Covers may not overlap. Touching is allowed.
Namuk may place up to $K$ covers, and he does not have to use them all.

Place the covers so that the sum of the rottenness of the uncovered eggs is as small as possible, then report that sum.

Input

The first line has the tray size $N$ and the number of covers $K$ , separated by a space. ( $1 \le N \le 2000$ , $1 \le K \le 8$ )

Each of the next $N$ lines has the rottenness $F$ of $N$ eggs, separated by spaces. ( $0 \le F \le 1000$ )

Output

Print the smallest possible sum of the rottenness of the uncovered eggs on the first line.

Examples2

Example 1
Input
```
3 1
2 7 6
9 5 1
4 3 8
```
Expected output
```
31
```
Example 2
Input
```
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
```
Expected output
```
17
```