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