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

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

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

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

textit

Гордість моряків

ldots

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

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

Тепер переходимо до задачі. Вона стане у пригоді туристам, які мають обмежений час і можуть лише побіжно подивитися деякі пам'ятки. Місто уявляється як прямокутна сітка розміру N \\times M, де кожна клітинка містить певну кількість пам'яток. Турист прагне переглянути якомога більше пам'яток, починаючи з будь-якої клітинки найпівнічнішого ряду та завершуючи у будь-якій клітинці найпівденнішого ряду. Переміщатися дозволяється лише трьома напрямками: на південь, на південний захід та на південний схід. Пам'ятайте, на карті північ — угорі, південь — унизу.

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

InputFile

У першому рядку знаходяться два числа $N$, $M$ (1 \\leq N, M \\leq 1000) — розміри сітки міста. Далі $N$ рядків по $M$ чисел — кількість пам'яток у кожній клітинці (не більше 10^5 у кожній, і не менше однієї). Наступний рядок — число $K$ (0 \\leq K \\leq N \\cdot M) — кількість клітинок, які турист бажає відвідати. У наступних $K$ рядках наведено по два числа — координати бажаної клітинки (рядки нумеруються від $1$ до $N$, стовпці — від $1$ до $M$). Гарантується, що клітинки не повторюються в списку.

OutputFile

Виведіть одне число — максимальну кількість пам'яток, через які можна пройти, відвідуючи всі бажані місця, або $-1$, якщо це неможливо.