Турист в Севастополе
Легендарный Севастополь,
Неприступный для врагов.
Севастополь, Севастополь –
Гордость русских моряков…
Севастополь (старогреческое - Херсонес) – город государственного значения Украины, город-герой. Расположен на юго-западе Крымского полуострова, на берегу Черного моря, исторический центр Севастополя расположен на южной стороне Севастопольской бухты.
В Севастополе очень большое количество достопримечательных мест: город Херсонес, памятник затопленным кораблям, Малахов Курган, памятник Матросу Кошке и много-много других. Некоторые гости говорят, что тут на каждом шагу что-то новое, что-то интересное и необычное. И они в большей степени правы.
Собственно, перейдем к задаче. Она будет очень полезна туристам, у которых мало времени, и они могут только бегло просмотреть некоторые достопримечательности. Представим город в виде прямоугольного поля размера N×M, каждая ячейка которого содержит некоторое число достопримечательностей. Наш турист хочет очень быстро посмотреть как можно большее количество достопримечательностей, потому он начнет в любой ячейке Северного ряда, а закончит обязательно в любой ячейке Южного ряда. При этом турист может передвигаться только в трех направлениях: в южном, юго-западном и юго-восточном. Напомним, что север находится в верхней части карты, а юг – в нижней.
И было бы все достаточно просто, если бы турист не нашел в интернете самые интересные места Севастополя. Теперь он, конечно, хочет обязательно их посетить. Помогите ему: по заданной карте с достопримечательностями, а также списком мест, которые турист хочет обязательно посмотреть, найдите максимальное количество достопримечательностей, которых он сможет посмотреть или выведите -1, если он не сможет обойти все желаемые места, двигаясь только в выбранных направлениях. Выходить за пределы города ему запрещается.
Входные данные
В первой строке содержится два числа N, M (1 ≤ N, M ≤ 1000) – количество участков города. Далее следует N строк, по M чисел в каждой – количество достопримечательностей в каждом участке (будем честными, в каждом участке не более 10^5 достопримечательностей, но и не менее одной, так как любые части природы тут обладают невероятной красотой). Далее следует число K (0 ≤ K ≤ N·M) – количество участков, которые желает посетить турист. В следующих K строках содержится по два числа – координаты i-го участка. Гарантируется, что участки не повторяются в его списке.
Выходные данные
В единственной строке выведите ответ на задачу или "-1", если обойти Севастополь, посетив все желаемые места, невозможно.