染染船长，扬帆起航！
在一系列准备工作做完后，染染的船终于出发了。
没过多久，染染就来到了一片复杂的海洋。这片海洋可以看成一个 n×mn×m 的网格，网格上的每个格点代表了一片海域。直线通过第 ii 行第 jj 列的海域需要花费 ti,jti,j 的时间。除此之外，如果需要转向，还需要额外花费 di,jdi,j 的时间，当然不管向左转向右转还是掉头都需要额外花费 di,jdi,j 的时间。也就是说，如果要通过第 ii 行第 jj 列的海域并且中途转向，则需要花费 ti,j+di,jti,j+di,j 的时间。
规定右方向为列增加的方向，下方向为行增加的方向。染染一开始向右驶入了这片海洋第 11 行第 11 列的海域，他想要从第 nn 行第 mm 列的海域向下驶出这片海洋，最快需要花费多少时间？
注意，通过这片海洋第 11 行第 11 列的海域和第 nn 行第 mm 列的海域花费的时间也要计算。
本题单个测试点内包含多组测试数据。
输入第一行一个正整数 T (1≤T≤20)T (1≤T≤20)，表示数据组数。
每组数据第一行两个正整数 n,m (1≤n×m≤105)n,m (1≤n×m≤105)，分别表示这片海洋的行数和列数。
接下来 nn 行，第 ii 行 mm 个非负整数 ti,1,ti,2,⋯,ti,m (0≤ti,j≤109)ti,1,ti,2,⋯,ti,m (0≤ti,j≤109)，表示直线通过的时间花费。
接下来 nn 行，第 ii 行 mm 个非负整数 di,1,di,2,⋯,di,m (0≤di,j≤109)di,1,di,2,⋯,di,m (0≤di,j≤109)，表示转向的时间花费。
保证单个测试点内每组数据中 n×mn×m 的和不超过 106106。
2
1 1
1
1
3 3
1 1 1
1 2 1
1 1 1
0 999 999
0 0 999
999 0 02
6
对于第一组样例，染染只需要转向通过第 11 行第 11 列的海域，花费时间 1+1=21+1=2。
对于第二组样例，染染要依次经过第 11 行第 11 列、第 22 行第 11 列、第 22 行第 22 列、第 33 行第 22 列、第 33 行第 33 列并在经过的每片海域处转向，花费时间 66。