P14236 [COI 2011] 主教 / LOVCI

译自 [COI 2011 T5](https://hsin.hr/hio2011/zadaci/)。

Mirko 画了一个 $2N$ 行 $2N$ 列的棋盘，并在上面玩以下游戏： 他在每个格子上写了一个整数，表示该格子的**价值**。他在第一行的中间并排放置了两个国际象棋的主教（分别位于第 $N$ 列和第 $N+1$ 列）。现在，Mirko 在思考每个主教能**看到**的格子：即位于该主教**所在对角线**上的所有格子（除了主教当前所在的格子本身）。 例如，如果 $N=3$，初始时两个主教（标记为 `L`）可以看到标记为 `X` 的 $10$ 个格子： ``` OOLLOO OXXXXO XXOOXX XOOOOX OOOOOO OOOOOO ``` 在给定的步数内，Mirko 试图通过以下方式获得尽可能高的分数： 1. 在走任何一步之前，Mirko 获得的分数等于两个主教从初始位置能**看到**的所有格子的价值之和。 2. 在每一步中，他选择其中一个主教，并将其沿对角线移动至该主教能**看到**的任意一个格子。 3. 在新位置上，主教现在可以看到一些从游戏开始至今**未被任何主教看到过**的新格子。这些新发现的格子的价值之和将被加到 Mirko 的分数中。 主教总是能看到所有与其在同一对角线上的格子，并且总是可以跳到这些格子中的任意一个。 请编写一个程序，计算 Mirko 在 $K$ 步之内能够获得的最大总分数。

第一行输入包含两个整数 $N$ 和 $K$ $(1 \le N \le 10, 0 \le K \le 100)$，分别是棋盘尺寸的一半和步数。 接下来的 $2N$ 行给出了棋盘每一行格子的价值：每行包含 $2N$ 个整数 $X$ $(-1,000,000 \le X \le 1,000,000)$，表示该行每个格子的价值。

输出一行一个整数，包含所求的最大分数。

对于 $40\%$ 的测试数据满足：$K \le 5$。