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.
def val_at(k,l):
	return a[k-1][l-1] if not(k>n or l>m) else -1

mn=raw_input()

n=int(mn.split(" ")[0])
m=int(mn.split(" ")[1])

a=[[0 for x in range(m)] for y in range(n)]

for i in range(n):
	r=raw_input()
	a[i]=[int(x) for x in r.split(" ")]

l=int(raw_input())

ij=[]

e1=0
e2=0
e1f=False
e2f=False

for i in range(l):
	r=raw_input()
	k=int(r.split(" ")[0])
	l=int(r.split(" ")[1])
	
	s1s=val_at(k,l)
	
	if(not e1f): 
		e1f=(s1s<0)
		e1=e1+s1s
	if(e1f):
		e1=-1	

	s2s=val_at(l,k)
	
	if(not e2f):  
		e2f=(s2s<0)
		e2=e2+s2s
	if(e2f):
		e2=-1	

print max(e1,e2)