P7231 [COCI 2015/2016 #3] DOMINO

「誕生日おめでとう！!」 小 M 收到了他女朋友的生日祝福和一份礼物。

小 M 的女朋友送小 M 了一张 $n \times n$ 的表格作为生日礼物，在表格的每个单元格中都写有一个非负整数。 不幸的是，有些单元格里数字太大了，小 M 不喜欢它们，所以他将在表格上面放置 $k$ 张骨牌，将覆盖那些数字太大的单元格。 更准确地说，小 M 按照以下规则放置骨牌。 - 骨牌为 $1\times 2$ 的矩形，不能拆开放置。 - 骨牌不重叠（但可以接触）。 - 所有可见（未覆盖）字段的总和需要尽可能的小。 您的任务是确定最小可见区域的数字的总和。数据保证可防止 $k$ 个骨牌且无重叠。

无

无

#### 数据规模及约定 对于 $100\%$ 的数据，$1\le n \le 2 \times 10 ^ 3$，$1\le k \le 8$，$0 \le a_i \le 10 ^ 3$。 #### 说明 翻译自 [COCI 2015-2016 #3 F DOMINO](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 160。