淘金棋与最强棋士

淘金棋与最强棋士

测试数据来自 system/2034

描述

现在小Q和小T要开始玩淘金棋,他们都想成为最强的棋士。

淘金棋的棋盘是 \(4\times 4\) 的方格,初始的时候每一个方格都放置了若干数量的金币。小Q先操作,之后是小T操作,二人交替操作。他们总计要操作 \(2k\) 次。

有一个记分牌子,一开始记分是零分。

对于一个玩家来说,他的每一次操作都可以选择一个 \(2\times 2\)的子区域,并将与这个子区域内金币数量相同的分数加到记分牌上,之后把这四个格子逆时针旋转 \(90\) 度(也就是修改了他们中金币的数量)。小Q的最终目的是最大化这个记分牌上的分数,而小T的最终目标是最小化这个记分牌上的分数。

已经知道小Q和小T都极致聪明,下面希望你能预测一下最终记分牌的得分。

格式

输入格式

输入含有多组数据,其中第一行给定一个整数 \(T~(1\le T\le 8)\) 表示之后会给出 \(T\) 组数据。

对于每一组数据,一共有五行,其中第一行给定了正整数 \(k\),表示他们二人分别要操作 \(k\) 次。

之后的四行中,每一行都给出四个正整数,描述了初始棋盘上金币的数量。

输出格式

一共输出 \(T\) 行,分别对应了 \(T\) 组数据,分别为每一组数据中预测的最终记分板上的数。

样例1

样例输入1

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

样例输出1

20
40
63
71

限制

对于 \(10\%\) 的数据,满足 \(1\le k\le 3\)。

对于 \(30\%\) 的数据,满足 \(1\le k\le 4\)。

对于 \(60\%\) 的数据,满足 \(1\le k\le 5\)。

对于 \(100\%\) 的数据,满足 \(1\le T\le 8\) 且 \(1\le k\le 6\),所有格子最初的金币个数一定是 \(1\) 到 \(10\) 的整数。

每一组数据时限为2秒。

信息

ID
1083
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者