题目描述
Sumeet has an N*N table, where a non-negative integer is written at each position (i,j) of the table.He wants to place J tiles on top of the table that will cover the fields that are too large.
But, there are certain conditions:
Each tile covers two positions of the table that are next to each
other (adjacent) either in a row or in a column.
The tiles can touch but not overlap.
The sum of all uncovered positions is to be minimized.
It will always be possible to place the J tiles without violating any of the above conditions.
Sumeet wants to determine the minimal sum of visible positions. As you are a great programmer, he asks you to help him out.
Input format
The first line of input contains two integers N dimension of the table and J, the number of tiles.
Each of the following N lines contains N integers describing the table.
Output format
Output the minimal sum of visible fields after covering the table with tiles.
Constraints
1 ≤ N ≤ 2000
1 ≤ J ≤ 8
1 ≤ integer value at each cell ≤ 1000
Note : There is no partial score for this problem
SAMPLE INPUT
3 1
2 7 6
9 5 1
4 3 8
SAMPLE OUTPUT
31
Explanation
Cover the cell (2,1) and (2,2) [ 1 - based indexing ]
输入格式
见题面
输出格式
见题面