uva737測資A

Input:
5
1 2 3 4
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
2
1 1 1 10
0 0 0 7
3
9 8 11 19
7 5 1 56
6 4 8 28
10
1 1 1 14
1 1 1 22
1 1 1 34
1 1 1 43
1 1 1 53
1 1 1 65
1 1 1 72
1 1 1 81
1 1 1 92
1 1 1 10
20
1 3 5 72
8 9 10 114
12 13 14 152
1 1 1 39
1 1 1 44
1 1 1 52
4 2 5 43
6 8 21 940
4 4 5 162
1 5 6 55
7 1 2 53
4 1 12 45
9 9 9 760
5 1 1 57
7 1 1 33
1 4 1 42
2 1 1 53
4 4 5 44
5 8 2 95
9 4 5 100
0
Output:
0
216
6859
1000
7644