题目描述

现在需要建造宫殿，建造要求如下：

甲方给了你一块 $N \times M$ 的网格区域，外边界上的墙已经修筑好了，除此以外，每两个水平或垂直相邻的格子之间可以建造一堵墙，建造每堵墙的花费都是已知的。

现在他要求你在这片网格区域上建造若干堵墙，形成一个网格迷宫。甲方将会把这个迷宫作为一个游乐设施，他们会把一些玩家随机扔进迷宫中，落在迷宫内的随机一点上，然后玩家需要走一条不重复经过任意点的路径，走到一个指定目标点。

甲方希望你的迷宫能够最大地限制玩家，也就是说，对于一个被随机扔进迷宫任意一点 $(x_1,\ y_1)$ 的人，无论他的指定目标点 $(x_2,\ y_2)$ 是迷宫的哪一点，他都有且只有唯一一条不重复路径能够抵达目标点。同时，在满足条件的前提下，甲方还希望你以最小的花费建墙。

在你完成建造后，甲方会要求你给出建造的花费，并评判是否合格。

现在，评测机就是你的甲方，由他来测评你能否将宫殿建造成功。

输入格式

一行一个整数 $T$ ，代表数据组数。

接下来 $T$ 组数据，对于每组数据：

首先给定两个正整数 $N$ 和 $M$ ，表示网格的大小。网格的左上角为 $(1,\ 1)$ ，右下角为 $(N,\ M)$ 。

接下来 $N \times M$ 行，每行给出两个非负整数 $cost(i,\ j,\ down)$ 和 $cost(i,\ j,\ right)$ ，表示一个网格点的下侧墙和右侧墙的建造花费，如果是外墙则花费固定为 $0$ （因为已经建好了）。输入的这些行依次表示坐标为 $(1,\ 1)$ , $(1,\ 2)$ , $...$ , $(1,\ M)$ , $(2,\ 1)$ , $...$ , $(N,\ 1)$ , $...$ , $(N,\ M)$ 的网格点的花费。

输出格式

输出共 $T​$ 行，每行一个整数，表示建造的最小花费。

样例

样例输入

1
3 3
1 9
7 8
4 0
2 6
12 5
3 0
0 10
0 11
0 0

样例输出

10

数据范围与提示

$1 \le N,\ M \le 500$

$0 \le cost \le 1000$

所有测试点中 $N \times M$ 的和 $\le 3 \cdot 10^5$ 。