eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 32 MiB

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

Неприступний ворогам.

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

Гордість нашим морякам…

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

У Севастополі дуже велика кількість видатних місць: місто Херсонес, пам'ятник затопленим кораблям, Малахов Курган, пам'ятник Матросу Кошкі та багато-багато інших. Деякі гості кажуть, що тут на кожному кроці щось нове, щось цікаве і незвичне. І вони у переважній більшості праві.

Власне, перейдемо до задачі. Вона буде дуже корисна туристам, у яких мало часу, і вони можуть лише похапцем переглянути деякі пам'ятки. Подамо місто у вигляді прямокутного поля розміром N×M, кожна комірка якого містить деяке число пам'яток. Наш турист хоче дуже швидко переглянути якомога більшу кількість пам'яток, тому він почне у довільній комірці Північного ряду, а завершить обов'язково у довільній комірці Південного ряду. При цьому турист може переміщуватись лише у трьох напрямках: у південному, південно-західному та південно-східному. Нагадаємо, що північ знаходиться у верхній частині карти, а південь – у нижній.

І було б усе достатньо просто, якби турист не знайшов у інтернеті самі цікаві місця Севастополя. Тепер він, звичайно, хоче обов'язковно їх відвідати. Допоможіть йому: за заданою картою з пам'ятками, а також списком місць, які турист хоче обов'язковно подивитись, знайдіть максимальну кількість пам'яток, які він зможе подивитись або виведіть -1, якщо він не зможе обійти усі бажані місця рухаючись лише у вказаних напрямках. Виходити за межі міста йому заборонено.

Вхідні дані

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

Вихідні дані

У єдиному рядку виведіть відповідь до задачі або "-1", якщо обійти Севастополь, відвідавши усі бажані місця, неможливо.

Приклад

Вхідні дані #1
3 3
1 2 3
7 4 6
5 2 1
1
2 2
Вихідні дані #1
12
Автор Олександр Бурков
Джерело III Відкрита Дистанційна Олімпіада 2013-2014 ім. В.Л.Дідковського