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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

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

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

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

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

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

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

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

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

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

输入格式

一行一个整数 ,代表数据组数。

接下来 组数据,对于每组数据:

首先给定两个正整数 ,表示网格的大小。网格的左上角为 ,右下角为

接下来 行,每行给出两个非负整数 ,表示一个网格点的下侧墙和右侧墙的建造花费,如果是外墙则花费固定为 (因为已经建好了)。输入的这些行依次表示坐标为 , , , , , , , , 的网格点的花费。

输出格式

输出共 行,每行一个整数,表示建造的最小花费。

样例

样例输入

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

样例输出

10

数据范围与提示

所有测试点中 的和