929 - Number Maze

在一個二維陣列迷宮，每個項以一個0~9的數字表示，如下所示。經上、下、左、右的移動過程中將所經過的數字作加總，請你從左上角(起點)到右下角(終點) 的所有可能路徑中，計算其數字總和最小的值為何。下圖的最小路徑數值總和為：0 + 3 + 1 + 4 + 5 + 4 + 2 + 5 = 24。

0	3	1	2	9
7	3	4	9	9
1	7	5	5	3
2	3	4	2	5

Problem

本題請你計算從左上角到右下角的路徑之最小數值總和，迷宮大小為NxM(1 <= N, M <= 999)。

Input

輸入資料的第一列有一個正整數表示測試資料的組數，每組資料的第一列為整數N，第二列為整數M，接下來有N列，每列有M個以一個空白字元隔開的整數，表示二維陣列的數值。

Output

請對每組測試資料輸出最小數值總和。

Sample Input

2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5

Sample Output

24
15

---

原文出處