313.DOMINO

小 M 的女朋友送小 M 了一张 $n \times n$ 的表格作为生日礼物，在表格的每个单元格中都写有一个非负整数。

不幸的是，有些单元格里数字太大了，小 M 不喜欢它们，所以他将在表格上面放置 $k$ 张骨牌，将覆盖那些数字太大的单元格。

更准确地说，小 M 按照以下规则放置骨牌。

• 骨牌为 $1\times 2$ 的矩形，不能拆开放置。
• 骨牌不重叠（但可以接触）。
• 所有可见（未覆盖）字段的总和需要尽可能的小。

您的任务是确定最小可见区域的数字的总和。数据保证可防止 $k$ 个骨牌且无重叠。

第一行，$2$ 个正整数 $n,k$，$n$ 表示表格的尺寸， $k$ 表示骨牌的数量。

接下来 $n$ 行，每一行都有 $n$ 个整数 $a_i$。这些 $n \times n$ 的数字的数字描述了 Mirko 的表格。

一行一个整数，最小可见区域的数字的总和。

对于 $100\%$ 的数据，$1\le n \le 2 \times 10 ^ 3$，$1\le k \le 8$，$0 \le a_i \le 10 ^ 3$。