Mirko 收到了一张 $N \times N$ 的网格图作为生日礼物，网格的每个格子里都写着一个非负整数。不幸的是，这些数字对 Mirko 来说太大了，所以他决定在网格上放置 $K$ 个骨牌，以覆盖那些数值过大的格子。

更具体地说，Mirko 按照以下规则放置骨牌：

• 每个骨牌覆盖网格中在同一行或同一列相邻的两个格子；
• 骨牌之间不能重叠（但可以接触）；
• 所有可见（未被覆盖）格子的数值之和需要尽可能小。

你的任务是求出可见格子数值之和的最小值。测试数据保证总是可以放置 $K$ 个互不重叠的骨牌。

输入格式

输入的第一行包含两个整数 $N$ ($1 \le N \le 2000$)，表示网格的尺寸，以及 $K$ ($1 \le K \le 8$)，表示骨牌的数量。

接下来的 $N$ 行，每行包含 $N$ 个介于 $[0, 1000]$ 之间的整数，描述 Mirko 的网格。

输出格式

输出的唯一一行应包含用骨牌覆盖网格后，可见格子数值之和的最小值。

子任务

在价值 70 分的测试用例中，满足 $K \le 5$。

样例

输入样例 1

3 1
2 7 6
9 5 1
4 3 8

输出样例 1

31

输入样例 2

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

输出样例 2

17

说明

样例 1 说明：我们放置骨牌使其覆盖写有数字 9 和 5 的格子。

样例 2 说明：我们放置骨牌使其覆盖第三列中数值为 $[4, 5]$ 和 $[5, 4]$ 的格子。