Tim_Duong

Nhân viên A cần đi từ điểm A đến điểm B bất kỳ nằm trong map cho trước, A = -1, B = -2.
Biết rằng Nhân viên A có thể đi theo 4 hướng trên, dưới, phải trái và mỗi bước đi sẽ mất 1 năng lượng với mỗi bước đi.
Trên bản đồ đi sẽ có điểm theo giá trị trong các ô.
Hãy tìm đường đi sao cho nhân viên đó đi từ A đến B tốn ít năng lượng nhất. Trong các đường đi tốn ít năng lượng nhất đó, hãy tìm đường đi để có nhiều điểm nhất.
A
1	1	1
1	3	1

1
1	1	1	1	1	2
1	1	1	6	1	1	1
7	1	1	1	1	1	1
1	1	1	1	1
1	1

8
1	1	1	5	10	B
 
Có rất nhiều đường đi từ A đến B và có mức năng lượng nhỏ nhất:
Đường màu đen, cam và xanh đều mất : 11 bước đi tương đương với 11 năng lương (do không vẽ được đường liền nhau nên vẽ tạm thế)
Tuy nhiên đường màu đen sẽ được: 36 point, Cam được: 19 point và Xanh sẽ được 13 point
Input:
T : tổng số testcase
N M: kích thước ma trận
Ma trận NxM
Output:
#Tc số điểm nhiều nhất
VD:
Input
1
6 7
-1 1 1 1 1 3 1
1 1 1 1 1 1 2
1 1 1 6 1 1 1
7 1 1 1 1 1 1
1 1 1 1 1 1 1
8 1 1 1 5 10 -2
Output:
#1 36