Mike is given a matrix A, N and M are numbers of rows and columns respectively. A1, 1 is the number in the top left corner. All the numbers in A are non-negative integers. He also has L pairs of integers (ik, jk). His task is to calculate Ai1, j1 + Ai2, j2 + ... + AiL, jL.


Unfortunately, Mike forgot if Ai, j was a number in the i'th row and j'th column or vice versa, if Ai, j was a number in the j'th row and i'th column.


So, Mike decided to calculate both E1 = Ai1, j1 + Ai2, j2 + ... + AiL, jL and E2 = Aj1, i1 + Aj2, i2 + ... + AjL, iL. If it is impossible to calculate E1(i.e. one of the summands doesn't exist), then let's assume, that it is equal to -1. If it is impossible to calculate E2, then let's also assume, that it is equal to -1.


Your task is to calculate max(E1, E2).


Input

The first line contains two integers N and M, denoting the number of rows and the number of columns respectively.
Each of next N lines contains M integers. The j'th integer in the (i + 1)'th line of the input denotes Ai, j.


The (N + 2)'th line contains an integer L, denoting the number of pairs of integers, that Mike has.
Each of next L lines contains a pair of integers. The (N + 2 + k)-th line in the input contains a pair (ik, jk).


Output
The first line should contain an integer, denoting max(E1, E2).

Examples
Input:
3 2
1 2
4 5
7 0
2
1 2
2 2
Output:
9

Input:
1 3
1 2 3
2
1 3
3 1
Output:
-1

Input:
1 3
1 2 3
2
1 1
3 1
Output:
4


Explanation

In the first test case N equals to 3, M equals to 2, L equals to 2. E1 = 2 + 5 = 7, E2 = 4 + 5 = 9. The answer is max(E1, E2) = max(7, 9) = 9;


In the second test case N equals to 1, M equals to 3, L equals to 2. It is impossible to calculate E1 and E2, because A3, 1 doesn't exist. So the answer is max(E1, E2) = max(-1, -1) = -1;


In the third test case N equals to 1, M equals to 3, L equals to 2. It is impossible to calculate E1, because A3, 1 doesn't exist. So E1 is equal to -1. E2 = 1 + 3 = 4. The answer is max(E1, E2) = max(-1,4) = 4.


Scoring

1 ≤ ik, jk ≤ 500 for each test case.


Subtask 1 (10 points): 1 ≤ N, M, L ≤ 5, 0 ≤ Ai, j ≤ 10;
Subtask 2 (12 points): 1 ≤ N, M, L ≤ 300, 0 ≤ Ai, j ≤ 10^6, all the numbers in A are equal;
Subtask 3 (20 points): 1 ≤ N, M, L ≤ 300, 0 ≤ Ai, j ≤ 10^9;
Subtask 4 (26 points): 1 ≤ N, M, L ≤ 500, 0 ≤ Ai, j ≤ 10^9;
Subtask 5 (32 points): 1 ≤ N, M ≤ 500, 1 ≤ L ≤ 250 000, 0 ≤ Ai, j ≤ 10^9.
# codeChef problem Code: MIKE1
m, n = map(int, raw_input().split() )
Given = []
for i in xrange( m ) :
    Given.append( map(int, raw_input().split() ) )
k = int( raw_input() )
flag1 = flag2 = 0
E1 = E2 = 0
for i in xrange( k ) :
    point = map(int, raw_input().split() )
    if ( flag1 == 1 or point[0] > m or point[1] > n ) :
        E1 = -1
        flag1 = 1
    else :
        E1 += Given[point[0] -1 ][point[1] - 1]
    if ( flag2 == 1 or point[1] > m or point[0] > n ) :
        E2 = -1
        flag2 = 1
    else :
        E2 += Given[point[1] -1 ][point[0] - 1]
    #print E1, ' ',E2
print max(E1, E2)