#1008. H. 开疆辟土，公司成立

由于公司发展需要，你来到北京开疆辟土，先后成立了“北京金湖量化科技有限公司”和“上海红墙泰和基金管理有限公司”。公司产品业绩傲人，屡获佳绩。

你常常受邀对投资人介绍你们公司：

北京金湖量化科技有限公司于2015年在北京成立，是一家高科技资产管理公司。创始人和主管来自国内外各大高校的资深量化研究和实战者，拥有全球视野及多年发达国家和发展中国家市场的量化投资经验，是中国最早一批进入量化投资行业的团队。公司运用前沿的金融理论研究，凭借全球市场长期的量化投资经验，依托先进的数据分析和建模技术，实现科学投资决策，为机构客户及高净值客户提供资产管理服务。

开疆辟土的过程中，需要建造自己的宫殿，建造要求如下：

甲方给了你一块 $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$ 。