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 ≤ 106, all the numbers in A are equal;

Subtask 3 (20 points): 1 ≤ N, M, L ≤ 300, 0 ≤ Ai, j ≤ 109;

Subtask 4 (26 points): 1 ≤ N, M, L ≤ 500, 0 ≤ Ai, j ≤ 109;

Subtask 5 (32 points): 1 ≤ N, M ≤ 500, 1 ≤ L ≤ 250 000, 0 ≤ Ai, j ≤ 109.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n , m = map(int,input().split(" "))
arr = []
for i in range(n):
    arr.append([int(j) for j in input().split()])
l = int(input())
check = []
for i in range(l):
    a, b = map(int,input().split())
    check.append([a-1,b-1])

e1 , e2 = 0 , 0
for i in range(l):
    if e1 != -1:
        if check[i][0] < n and check[i][1] < m:
            e1 += arr[check[i][0]][check[i][1]]
        else:
            e1 = -1
    if e2 != -1:
        if check[i][0] < m and check[i][1] < n:
            e2 += arr[check[i][1]][check[i][0]]
        else:
            e2 = -1
print(max(e1,e2))

N,M=map(int,input().split())
arr=[]
for i in range(0,N):
    k=list(map(int,input().split()))
    arr.append(k)
E1=0
E2=0
L=int(input())
f1=0
f2=0
for j in range(0,L):
    a,b=map(int,input().split())
    if(a>(N) or b>(M)):
        E1= (-1)
        f1=1
    elif(f1==0):
        E1+=arr[a-1][b-1]
    if(b>(N) or a>(M)):
        E2= (-1)
        f2=1
    elif(f2==0):
        E2+=arr[b-1][a-1]
print(max(E1,E2))
        

n,m=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
ans1=0
ans2=0
k=int(input())
c=0
d=0
for i in range(k):
    a,b=map(int,input().split())
    try:
        ans1+=l[a-1][b-1]
    except:
        c=1
    try:
        ans2+=l[b-1][a-1]
    except:
        d=1
if c:
    ans1=-1
if d:
    ans2=-1
print(max(ans1,ans2))
    


l = []
n,m = map(int,input().split())

for i in range(n):
    k = list(map(int,input().split()))
    l.append(k)

e1 = 0
e2 = 0

n1 = int(input())
flag1,flag2 = 0,0
for i in range(n1):
    a,b = map(int,input().split())
    if a<=n and b<=m and flag1 == 0:
      e1+=l[a-1][b-1]
    else:
        e1 = -1
        flag1 = 1

    if b<=n and a<=m and flag2 == 0:
        e2+=l[b-1][a-1]
    else:
        e2 = -1
        flag2 = 1

print(max(e1,e2))






# cook your dish here

l = []
n,m = map(int,input().split())

for i in range(n):
    k = list(map(int,input().split()))
    l.append(k)

e1 = 0
e2 = 0

n = int(input())
flag1,flag2 = 0,0
for i in range(n):
    a,b = map(int,input().split())
    if a<=n and b<=m and flag1 == 0:
      e1+=l[a-1][b-1]
    else:
        e1 = -1
        flag1 = 1

    if b<=n and a<=m and flag2 == 0:
        e2+=l[b-1][a-1]
    else:
        e2 = -1
        flag2 = 1

print(max(e1,e2))