给定一个$Ｎ * Ｎ$的矩阵，每个格子中有一个数字，再给你K个1 * 2的多米诺骨牌，你可以用这些骨牌挡住格子中的一个数字，骨牌只能正好占两格且不能重叠，求能看得见的数字的和的最小值是多少？
输入：
第一个两个数N（$1<=N<=2000$）和Ｋ（$1<=K<=8$）.
接下来Ｎ行，每行Ｎ个数，表示矩阵，每个格子的值，大于等于0，小于等于1000
输出：
一行一个数，表示最小的可见数字之和。
70%的数据$K<=5$
SAMPLE TESTS

input
3 1
2 7 6
9 5 1
4 3 8
Output
31
input
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
Output
17