Mike and Matrices

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Mike is given a matrix A, N and M are numbers of rows and columns respectively. A_{1, 1} is the number in the top left corner. All the numbers in A are nonnegative integers. He also has L pairs of integers (i_{k}, j_{k}). His task is to calculate A_{i1, j1} + A_{i2, j2} + ... + A_{iL, jL}.
Unfortunately, Mike forgot if A_{i, j} was a number in the i'th row and j'th column or vice versa, if A_{i, j} was a number in the j'th row and i'th column.
So, Mike decided to calculate both E_{1} = A_{i1, j1} + A_{i2, j2} + ... + A_{iL, jL} and E_{2} = A_{j1, i1} + A_{j2, i2} + ... + A_{jL, iL}. If it is impossible to calculate E_{1}(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 E_{2}, then let's also assume, that it is equal to 1.
Your task is to calculate max(E_{1}, E_{2}).
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 A_{i, 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 (i_{k}, j_{k}).
Output
The first line should contain an integer, denoting max(E_{1}, E_{2}).
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. E_{1} = 2 + 5 = 7, E_{2} = 4 + 5 = 9. The answer is max(E_{1}, E_{2}) = 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 E_{1} and E_{2}, because A_{3, 1} doesn't exist. So the answer is max(E_{1}, E_{2}) = 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 E_{1}, because A_{3, 1} doesn't exist. So E_{1} is equal to 1. E_{2} = 1 + 3 = 4. The answer is max(E_{1}, E_{2}) = max(1,4) = 4.
Scoring
1 ≤ i_{k}, j_{k} ≤ 500 for each test case.
Subtask 1 (10 points): 1 ≤ N, M, L ≤ 5, 0 ≤ A_{i, j} ≤ 10;
Subtask 2 (12 points): 1 ≤ N, M, L ≤ 300, 0 ≤ A_{i, j} ≤ 10^{6}, all the numbers in A are equal;
Subtask 3 (20 points): 1 ≤ N, M, L ≤ 300, 0 ≤ A_{i, j} ≤ 10^{9};
Subtask 4 (26 points): 1 ≤ N, M, L ≤ 500, 0 ≤ A_{i, j} ≤ 10^{9};
Subtask 5 (32 points): 1 ≤ N, M ≤ 500, 1 ≤ L ≤ 250 000, 0 ≤ A_{i, j} ≤ 10^{9}.
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/MIKE1 
Tags  cakewalk implementation kostya_by ltime07 
Date Added:  28112013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 