eolymp
bolt
Try our new interface for solving problems
Problems

Турист в Севастополе

Турист в Севастополе

Time limit 2 seconds
Memory limit 32 MiB

Легендарный Севастополь,

Неприступный для врагов.

Севастополь, Севастополь –

Гордость русских моряков…

Севастополь (старогреческое - Херсонес) – город государственного значения Украины, город-герой. Расположен на юго-западе Крымского полуострова, на берегу Черного моря, исторический центр Севастополя расположен на южной стороне Севастопольской бухты.

В Севастополе очень большое количество достопримечательных мест: город Херсонес, памятник затопленным кораблям, Малахов Курган, памятник Матросу Кошке и много-много других. Некоторые гости говорят, что тут на каждом шагу что-то новое, что-то интересное и необычное. И они в большей степени правы.

Собственно, перейдем к задаче. Она будет очень полезна туристам, у которых мало времени, и они могут только бегло просмотреть некоторые достопримечательности. Представим город в виде прямоугольного поля размера N×M, каждая ячейка которого содержит некоторое число достопримечательностей. Наш турист хочет очень быстро посмотреть как можно большее количество достопримечательностей, потому он начнет в любой ячейке Северного ряда, а закончит обязательно в любой ячейке Южного ряда. При этом турист может передвигаться только в трех направлениях: в южном, юго-западном и юго-восточном. Напомним, что север находится в верхней части карты, а юг – в нижней.

И было бы все достаточно просто, если бы турист не нашел в интернете самые интересные места Севастополя. Теперь он, конечно, хочет обязательно их посетить. Помогите ему: по заданной карте с достопримечательностями, а также списком мест, которые турист хочет обязательно посмотреть, найдите максимальное количество достопримечательностей, которых он сможет посмотреть или выведите -1, если он не сможет обойти все желаемые места, двигаясь только в выбранных направлениях. Выходить за пределы города ему запрещается.

Input data

В первой строке содержится два числа N, M (1N, M1000) – количество участков города. Далее следует N строк, по M чисел в каждой – количество достопримечательностей в каждом участке (будем честными, в каждом участке не более 10^5 достопримечательностей, но и не менее одной, так как любые части природы тут обладают невероятной красотой). Далее следует число K (0KN·M) – количество участков, которые желает посетить турист. В следующих K строках содержится по два числа – координаты i-го участка. Гарантируется, что участки не повторяются в его списке.

Output data

В единственной строке выведите ответ на задачу или "-1", если обойти Севастополь, посетив все желаемые места, невозможно.

Examples

Input example #1
3 3
1 2 3
7 4 6
5 2 1
1
2 2
Output example #1
12
Author Александр Бурков
Source III Открытая Дистанционная Олимпиада 2013-2014 им. В.Л.Дидковского