Problem1500--XP的矩阵

1500: XP的矩阵

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

XP学长觉得矩阵很美,虽然他也不知道美在哪里,因此,他决定挖掘一下矩阵的美。现在给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,将路径上的所有数字累加起来作为这条路径的路径和。XP学长决定编写一个程序来求所有路径和中的最小路径和。例如,下面矩阵中的路径1-3-1-0-6-1-0是所有路径中路径和最小的,返回结果是12。
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

Input

输入包含多组测试用例,第一行输入一个T表示测试数据组数,(1<=T<=15)
接下来有T组数据,每组先输入两个整数M,N接下来输入M*N的矩阵(1<=N,M<=1000),且最终结果在int范围内。

Output

输出路径和的最小值。

Sample Input Copy

1
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

Sample Output Copy

12