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: MEDIUM
Tags: Implementation

Starter code:

Solutions:
(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))


temp = list(map(int, input().split()))
n = temp[0]
m = temp[1]
mat = []
for i in range(n):
	mat.append(list(map(int, input().split())))
l = int(input())
e1 = 0
e2 = 0
for t in range(l):
	pair = list(map(int, input().split()))
	i = pair[0] - 1
	j = pair[1] - 1
	if e1 != -1:
		if i >= 0 and j >= 0 and (i < n) and (j < m):
			e1 += mat[i][j]
		else:
			e1 = -1
	if e2 != -1:
		if i >= 0 and j >= 0 and (i < m) and (j < n):
			e2 += mat[j][i]
		else:
			e2 = -1
print(max(e1, e2))


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))


(n, m) = map(int, input().split())
matrix = []
for _ in range(n):
	matrix.append([int(x) for x in input().split()])
k = int(input())
pairs = []
for _ in range(k):
	pairs.append([int(x) for x in input().split()])
(E1, E2) = (0, 0)
for i in range(k):
	(x, y) = (pairs[i][0], pairs[i][1])
	if x > n or y > m:
		E1 = -1
		break
	else:
		E1 += matrix[x - 1][y - 1]
for i in range(k):
	(x, y) = (pairs[i][0], pairs[i][1])
	if x > m or y > n:
		E2 = -1
		break
	else:
		E2 += matrix[y - 1][x - 1]
print(max(E1, E2))


(n, m) = input().split()
n = int(n)
m = int(m)
A = []
for i in range(n):
	A.append([int(x) for x in input().split()])
e1 = 0
e2 = 0
k = int(input())
for i in range(k):
	(x, y) = input().split()
	x = int(x) - 1
	y = int(y) - 1
	if e1 > -1 and x < n and (y < m):
		e1 += A[x][y]
	else:
		e1 = -1
	if e2 > -1 and x < m and (y < n):
		e2 += A[y][x]
	else:
		e2 = -1
print(max(e1, e2))


A = []
(n, m) = map(int, input().split())
for i in range(n):
	A_row = list(map(int, input().split()))
	A.append(A_row)
(e1, e2) = (0, 0)
l = int(input())
(flag1, flag2) = (True, True)
for i in range(l):
	(a, b) = map(int, input().split())
	if a <= n and b <= m and flag1:
		e1 += A[a - 1][b - 1]
	else:
		e1 = -1
		flag1 = False
	if b <= n and a <= m and flag2:
		e2 += A[b - 1][a - 1]
	else:
		e2 = -1
		flag2 = False
print(max(e1, e2))


(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) = [int(x) for x in input().split()]
m = []
for i in range(N):
	n = [int(x) for x in input().split()]
	m.append(n)
L = int(input())
E_1 = 0
E_2 = 0
e_1 = False
e_2 = False
for t in range(L):
	(i, j) = [int(x) for x in input().split()]
	try:
		E_1 += m[i - 1][j - 1]
	except:
		e_1 = True
	try:
		E_2 += m[j - 1][i - 1]
	except:
		e_2 = True
if e_1 == True:
	E_1 = -1
if e_2 == True:
	E_2 = -1
print(max(E_1, E_2))


(n, m) = map(int, input().split())
matrix = []
for i in range(0, n):
	new = list(map(int, input().split()))
	matrix.append(new)
l = int(input())
pairs = []
for i in range(0, l):
	new = list(map(int, input().split()))
	pairs.append(new)
e1 = e2 = 0
for i in pairs:
	try:
		e1 += matrix[i[0] - 1][i[1] - 1]
	except:
		e1 = -1
		break
for i in pairs:
	try:
		e2 += matrix[i[1] - 1][i[0] - 1]
	except:
		e2 = -1
		break
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))


(nrow, ncol) = map(int, input().split())
a = []
for _ in range(nrow):
	a.append(list(map(int, input().split())))
e1 = e2 = 0
l = int(input())
for _ in range(l):
	(i, j) = map(int, input().split())
	(i, j) = (i - 1, j - 1)
	if e1 != -1 and i < nrow and (j < ncol):
		e1 += a[i][j]
	else:
		e1 = -1
	if e2 != -1 and j < nrow and (i < ncol):
		e2 += a[j][i]
	else:
		e2 = -1
print(max(e1, e2))


(rows, cols) = map(int, input().split())
arr = []
E1 = 0
E2 = 0
for i in range(rows):
	col = list(map(int, input().split()))
	arr.append(col)
q = int(input())
for i in range(q):
	(i, j) = map(int, input().split())
	if i > rows or j > cols or E1 == -1:
		E1 = -1
	else:
		E1 += arr[i - 1][j - 1]
	if i > cols or j > rows or E2 == -1:
		E2 = -1
	else:
		E2 += arr[j - 1][i - 1]
print(max(E1, E2))


line = input().split()
(row, col) = (int(line[0]), int(line[1]))
A = []
for i in range(row):
	A.append([int(x) for x in input().split()])
l = int(input())
P = []
for i in range(l):
	P.append([int(x) for x in input().split()])
E1 = 0
E2 = 0
for el in P:
	if E1 >= 0 and el[0] <= row and (el[1] <= col):
		E1 = E1 + A[el[0] - 1][el[1] - 1]
	else:
		E1 = -1
	if E2 >= 0 and el[0] <= col and (el[1] <= row):
		E2 = E2 + A[el[1] - 1][el[0] - 1]
	else:
		E2 = -1
print(max(E1, E2))


class MatrixTest(object):

	def __init__(self):
		self.valid = True
		self.vals_sum = 0

	def add_el(self, matrix, row, col):
		if self.valid:
			try:
				self.vals_sum += matrix[row][col]
			except IndexError:
				self.valid = False
				self.vals_sum = -1
(n, m) = (int(x) for x in input().split())
matrix = []
for _ in range(n):
	matrix.append(tuple((int(x) for x in input().split())))
transpose_matrix = list(zip(*matrix))
l = int(input())
m1 = MatrixTest()
m2 = MatrixTest()
for _ in range(l):
	(a, b) = (int(x) - 1 for x in input().split())
	m1.add_el(matrix, a, b)
	m2.add_el(transpose_matrix, a, b)
print(max(m1.vals_sum, m2.vals_sum))


(n, m) = map(int, input().split())
mat = [list(map(int, input().split())) for i in range(n)]
l = int(input())
flage1 = 0
flage2 = 0
e1 = 0
e2 = 0
for i in range(l):
	(i, j) = map(int, input().split())
	i = i - 1
	j = j - 1
	if flage1 == 0:
		if i < n and j < m:
			e1 = e1 + mat[i][j]
		else:
			e1 = -1
			flage1 = 1
	if flage2 == 0:
		if j < n and i < m:
			e2 = e2 + mat[j][i]
		else:
			e2 = -1
			flage2 = 1
print(max(e1, e2))