Turist Sevastopolda

textitƏfsanəvi Sevastopol,

textitDüşmənlərə keçilməz.

textitSevastopol, Sevastopol –

textit

Dənizçilərin qüruru

ldots

Sevastopol (tarixən qədim yunan dilində "Xersones" kimi tanınır) — Ukraynanın dövlət əhəmiyyətli qəhrəman şəhəridir. O, Krım yarımadasının cənub-qərbində, Qara dəniz sahilində yerləşir, tarixi mərkəzi isə Sevastopol körfəzinin cənub tərəfində yerləşir.

Sevastopol zəngin görməli yerlərə malikdir: antik Xersones şəhəri, Batmış Gəmilər abidəsi, Malaxov kurqanı, Matros Koşka abidəsi və daha nələr-nələr. Ziyarətçilər tez-tez qeyd edirlər ki, hər addımda burada yeni, maraqlı və qeyri-adi bir şey var. Bu tez-tez doğrudur.

İndi isə məsələyə keçək. Bu, vaxtı məhdud turistlər üçün xüsusilə faydalı olacaq, çünki onlar yalnız bəzi abidələri qısa müddətdə görə bilərlər. Şəhər \\mathbf{N} \\times \\mathbf{M} ölçülü düzbucaqlı tor kimi təsvir olunur, burada hər hüceyrə müəyyən sayda abidə saxlayır. Turist mümkün qədər çox abidə görmək istəyir və istənilən Şimal cərgəsinin hüceyrəsindən başlayıb istənilən Cənub cərgəsinin hüceyrəsində bitirə bilər. Turist yalnız üç istiqamətdə hərəkət edə bilər: cənub, cənub-qərb və cənub-şərq. Unutmayın, xəritədə şimal yuxarıda, cənub isə aşağıdadır.

Məsələ sadə olardı, əgər turist internetdə Sevastopolun ən maraqlı yerlərini tapmasaydı. İndi o, əlbəttə ki, onların hamısını görmək istəyir. Sizin vəzifəniz: xəritə üzrə abidə sayları və ziyarət etmək istədiyi xüsusi yerlərin siyahısı verildikdə, turist bütün həmin yerləri ziyarət edərək görə biləcəyi maksimum abidə sayını müəyyənləşdirin. Əgər yalnız icazə verilmiş istiqamətlərdə hərəkət etməklə bütün arzulanan yerləri ziyarət etmək mümkün deyilsə, \\mathbf{-1} çıxarın. Turist şəhərin hüdudlarından kənara çıxa bilməz.

InputFile

Birinci sətrdə iki tam ədəd \\mathbf{N}, \\mathbf{M} (1 \\leq \\mathbf{N}, \\mathbf{M} \\leq 1000) — şəhər torunun ölçüləri verilir. Sonra hər birində \\mathbf{M} ədəd olmaqla \\mathbf{N} sətir gəlir — hər hüceyrədəki abidə sayı verilir (hər bir hüceyrədə ən çoxu 10^5 abidə var, ən azı isə bir abidə). Sonra \\mathbf{K} (0 \\leq \\mathbf{K} \\leq \\mathbf{N} \\cdot \\mathbf{M}) — turistin ziyarət etmək istədiyi xüsusi yerlərin sayı verilir. Növbəti \\mathbf{K} sətirin hər birində iki tam ədəd — tələb olunan hüceyrələrin koordinatları (sətr və sütun 1-dən \\mathbf{N} və \\mathbf{M}-ə kimi nömrələnir). Siyahıdakı hüceyrələr təkrarlanmır.

OutputFile

Yeganə sətirdə cavabı — turistin bütün arzulanan yerləri ziyarət edərək görə biləcəyi maksimum abidə sayını, əgər mümkün deyilsə, \\mathbf{-1} çıxarın.