景区建设

Problem Description

CF （Construct Foothill） 是一款模拟经营类型的游戏。玩家将扮演一位建筑师，对一块山麓地区进行景区建设。 而一块山麓地区由一块 $n \times m$ 的区域（ $n$ 行 $m$ 列）来表示，其中，每块区域 （$i, j$） 都有一个高度 $a_{ij}$ 。对于游客而言，他们每步只能走到相邻的区域。游客不喜欢费力的旅行，所以他们只会从高的区域到低的区域，因为从低到高实在是太累了。而且作为崎岖的山区，没有两个的地区有相同的高度。但是寸土寸金，游客如果能多到达一块区域，就能多赚一大笔钱，你的老板知道了后，命令你建设这个山区成为景区并且所有区域都能从入口到达，否则不给你发工资。 但作为建筑师，当然有自己的看家本领，你可以建设传送器来帮忙克服游客的困难。传送器可以搭建在任意的区域，但是传送器相当昂贵，一个就要 $2^{34}$ 元 ，而且为了确保传送的稳定性，以及预防不同地区电磁干扰，如果要开通两个区域的传送器之间的传送线路，还需要一定的建设成本，这都需要你自掏腰包。 （$x_1, y_1$） 和 （$x_2, y_2$） 之间搭建传送线路的价格为: $114|x_1 - x_2| + 5141|y_1 - y_2|+ 919810|a_x - a_y| $ 已知所有游客都从左上角 （$1, 1$） 作为景区入口，而且老板大发慈悲在入口免费帮你建了一个传送器，希望所有游客都能从入口到达这个景区的任意一个区域。你作为建筑师，想要尽可能的减少成本，又要完成老板的指标，请问最少要花多少钱。

Input

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ （ $1 \le t \le 20$ ）。测试用例说明如下。 每个测试样例的第一行包含用空格分隔的两个数 $n$ 和 $m$ （ $1 \le n \le 100$, $1 \le m \le 100$）. 接下来 $n$ 行，有每行有 $m$ 个数。其中，第 $i$ 行的第 $j$ 个数即为 $a_{ij}$ （ $1 \le a_{ij} \le 10000$ ）.

Output

对于每个测试用例，输出一个整数，表示完成任务的最小成本。

Sample Input

2
2 2
1 2
3 4
2 3
1 5 4
2 3 6

Sample Output

17182633869
34364347814

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）