Problem P: 旅游5

Problem P: 旅游5

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

某地有个n*m的迷宫,奥利奥打算去玩,很可惜,我们比他先到,我们打算对迷宫动点手脚,使奥利奥不能从出口出去。迷宫的规则为:从(1,1)进,(n*m)出,-1为墙不能通过。我们可以在他进入迷宫前选一些路给堵上,堵路的规则:权值为0的路不能堵,权值为-1为墙,不用堵,赌路的花费为路的权值。求出堵路的在最小花费。

Input

输入的第一行有三个正整数Q,N,M。
代表接下来有Q组数据,这Q组数据都是N*M的迷宫。
接下来每组数据各N行,代表一个迷宫,每行各M个整数,第i行中的第j个整数代表迷宫座标(i,j)的路。
1<=Q<=5*103
1<=Q*N*M<=2.5*105
1<=N,M<=500
代表迷宫格子的数字为介于-1和109间的整数(包含-1和109)
每个迷宫中,代表座标(1,1)和(N,M)的格子的数字一定是0

Output

每一组数据输出一行,如果无论如何奥利奥都能到达终点,请在这一行中输出-1,否则请在这一行中输出一个代表答案的整数。

Sample Input Copy

3 3 3
0 2 2
3 2 3
2 2 0
0 1 2
-1 1 -1
2 1 0
0 1 2
0 0 0
2 1 0

Sample Output Copy

6
1
-1