描述

染染船长，扬帆起航！

在一系列准备工作做完后，染染的船终于出发了。

没过多久，染染就来到了一片复杂的海洋。这片海洋可以看成一个 $n \times m$ 的网格，网格上的每个格点代表了一片海域。直线通过第 $i$ 行第 $j$ 列的海域需要花费 $t_{i,j}$ 的时间。除此之外，如果需要转向，还需要额外花费 $d_{i,j}$ 的时间，当然不管向左转向右转还是掉头都需要额外花费 $d_{i,j}$ 的时间。也就是说，如果要通过第 $i$ 行第 $j$ 列的海域并且中途转向，则需要花费 $t_{i,j} + d_{i,j}$ 的时间。

规定右方向为列增加的方向，下方向为行增加的方向。染染一开始向右驶入了这片海洋第 1 行第 1 列的海域，他想要从第 $n$ 行第 $m$ 列的海域向下驶出这片海洋，最快需要花费多少时间？注意，通过这片海洋第 1 行第 1 列的海域和第 $n$ 行第 $m$ 列的海域花费的时间也要计算。

输入描述

本题单个测试点内包含多组测试数据。

• 输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。
• 每组数据第一行两个正整数 $n, m$ ($1 \leq n \times m \leq 10^5$)，分别表示这片海洋的行数和列数。
• 接下来 $n$ 行，第 $i$ 行 $m$ 个非负整数 $t_{i,1}, t_{i,2}, \cdots, t_{i,m}$ ($0 \leq t_{i,j} \leq 10^9$)，表示直线通过的时间花费。
• 接下来 $n$ 行，第 $i$ 行 $m$ 个非负整数 $d_{i,1}, d_{i,2}, \cdots, d_{i,m}$ ($0 \leq d_{i,j} \leq 10^9$)，表示转向的时间花费。
• 保证单个测试点内每组数据中 $n \times m$ 的和不超过 $10^6$。

输出描述

对于每组数据输出一行一个非负整数，表示花费的最少时间。

样例

2
1 1
1
1
3 3
1 1 1
1 2 1
1 1 1
0 999 999
0 0 999
999 0 0

2
6

提示

• 对于第一组样例，染染只需要转向通过第 1 行第 1 列的海域，花费时间 $1 + 1 = 2$。
• 对于第二组样例，染染要依次经过第 1 行第 1 列、第 2 行第 1 列、第 2 行第 2 列、第 3 行第 2 列、第 3 行第 3 列，并在经过的每片海域处转向，花费时间 $6$。