Ryan and Katie love drinking and one day Ryan gets lost and unconscious after drinking. They live on a N*M grid and Katie is on the cell (1,1) and Ryan is on (N,M).

Each cell consists of some value A[i][j], which denotes the score for that particular cell. Katie starts walking and has to reach Ryan with maximum possible score. Her score is denoted by sum of score of all the cells that she visits in her path. The only directions she can move are right or down.

Each cell also has two values : H[i][j] and V[i][j]. H[i][j] denotes that if she passes the cell (i, j) then the maximum contiguous steps in the horizontal direction from (i, j) must be less than or equal to H[i][j] (So if she moves H[i][j] contiguous horizontal steps from cell (i, j) then she must turn her direction). Similarly V[i][j] denote the maximum contiguous steps in the vertical direction possible from (i, j).

Calculate the maximum possible score Katie can obtain while saving Ryan without violating any H[i][j] and V[i][j] in her path, or else print "-1" (without quotes) if there's no way to reach cell (N, M) without making a violation.

Input format :

The first line contains integer T denoting number of Test cases.

The first line of each test case contains N and M, the size of the grid.

The next N lines contain M integers each corresponding to A[i][j].

The next N lines contain M integers each corresponding to H[i][j].

The next N lines contain M integers each corresponding to V[i][j].

Output Format :

Print a single integer corresponding to the answer of each test case or "-1" (without quotes) if it is impossible.

Constraints :

1 ≤ T ≤ 3

1 ≤ N, M ≤ 180

1 ≤ A[i][j] ≤ 50

1 ≤ H[i][j] ≤ M

1 ≤ V[i][j] ≤ N

Sample Input :

1

3 3

4 1 1

2 1 1

4 2 1

1 1 1

2 2 1

2 2 2

1 2 2

1 2 2

2 2 2

Sample Output :

10

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

1 month ago

cpp

0.94 sec

126252 KB

1 month ago

cpp

0.07 sec

64 KB