【题目描述】 有一天， 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列的格子上的数ai,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，都有ai,j=1。
对于另外10%的数据，对于任意i,j，都有ai,j≤1。
对于75%的数据，n,m≤50，对于任意i,j，都有0≤ai,j≤9。
对于100%的数据，T≤10，1≤n,m≤100，对于任意i,j，都有0≤ai,j≤10000。