题目背景

「誕生日おめでとう！!」

小 M 收到了他女朋友的生日祝福和一份礼物。

题目描述

小 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 的表格。

输出格式

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

3 1
2 7 6
9 5 1
4 3 8

31

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

17

提示

数据规模及约定

对于 $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，满分 160。