有一天， 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\n3 5\n6 6 6 6 6 \n1 2 3 4 5\n2 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$。