题目背景

译自 COI 2011 T5。

题目描述

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)$，表示该行每个格子的价值。

输出格式

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

2 0 
0 -9 -9 0 
0 1 1 0 
1 0 0 1 
0 0 6 0 

4

2 1 
0 -9 -9 0 
0 1 1 0 
1 0 0 1 
0 0 6 0 

1

提示

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