题目描述

有一天， Alice和Bob在一个n行m列的棋盘上玩一个叫做“跳跳棋”的游戏，每一个格子上有一个数字。 最开始，Alice在第一行的任意一个格子放一个棋子，并在自己的罚分中加上该格子上的数字。 接下来进行若干轮操作，每轮操作有以下两步： ①Bob可以选择两个上下相邻的格子，在它们之间放上一堵墙。Bob每次操作时，可以修建多堵墙，也可以不修建。但是不能让Alice所在的格子与第$n$行不连通。 ②Alice将自己的棋子向上下左右方向与其相邻的四个移动一步，并在自己的罚分中加上移动到的格子上的数字。但是若两个格子之间有墙挡住，则不能往这个格子走。 若某一轮操作后Alice的棋子到了第$n$行，游戏结束。 Alice的目的是让自己的罚分尽量小，Bob的目的是让Alice的罚分尽量大。 我们已知Alice和Bob都是“聪明绝顶”的，即他们都能做出对自己最优的决策，那么请问最后Alice的罚分是多少。

输入

本题包含多组数据，第一行一个整数$T$表示数据组数。接下来依次描述各组数据，对于每组数据： 第一行$2$个整数$n，m$，描述棋盘大小。 接下来$n$行，每行$m$个整数，其中第$i$行第$j$个数描述了棋盘上第$i$行第$j$列的格子上的数$a_i,j$。

输出

对于每组数据，输出一行一个整数，表示在两人都“聪明绝顶”的情况下，Alice最终的罚分是多少。

输入样例

1
2 2
1 2
3 4

输出样例

6

提示

【输入样例2】

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

【输出样例2】

47

【数据规模】 对于5%的数据，$n=1$。 对于15%的数据，$n≤2$。 对于另外20%的数据，$m≤15$。 对于另外5%的数据，对于任意$i,j$，都有$a_{i,j}=1$。 对于另外10%的数据，对于任意$i,j$，都有$a_{i,j}≤1$。 对于75%的数据，$n,m≤50$，对于任意$i,j$，都有$0≤a_{i,j}≤9$。 对于100%的数据，$T≤10，1≤n,m≤100$，对于任意$i,j$，都有$0≤a_{i,j}≤10000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。