Master Oogway

Barış MIT-yə təhsil almağa gedərkən, tısbağası Oogwayi də özü ilə apardı. Ustad Oogway çox ağıllı tısbağadır və sahibi Barış kimi o da getdiyi hər yerdə alqoritmik məsələlər həll etməyi xoşlayır. Barış Oogwaylə birlikdə MIT-nin həyətində gəzintiyə çıxarkən damalara bölünmüş $nxm$ ölçülü düzbucaqlı formasında bir ərazi gördü. Bu ərazidə sol yuxarı xananı $(1,1)$, sağ aşağı xananı isə $(n,m)$ ilə işarə edəcəyik. Oogwayin zəkasını yoxlamaq məqsədi ilə Barış, ərazidə müəyyən xanalarda qəpiklər yerləşdirdi və Oogway $(1,1)$ xanasından başlayaraq hər addımda yalnız sağa və ya aşağıya getməklə bu qəpikləri yığmalıdır. Aydın məsələdir ki, bir dəfədə bütün qəpikləri yığmaq mümkün olmaya bilər. Buna görə də onlar hər gün bu yerə gəlirlər və Oogway gündə bir dəfə $(1,1)$ xanasından başlayaraq hərəkət edir və müəyyən sayda qəpik yığır. Barışı bir sual düşündürür, Oogway minimum neçə günə bütün qəpikləri yığa bilər?

Giriş verilənləri

Birinci sətirdə iki tam ədəd $n$ ( $1\le n\le 10^9$ ) və $m$ ( $1\le m\le 10^9$ ) – uyğun olaraq düzbucaqlı ərazidəki sətir və sütunların sayı. İkinci sətirdə bir tam ədəd $q$ ( $1\le q\le 10^5$ ) – qəpiklərin sayı. Növbəti $q$ ( $1\le q\le 10^5$ ) sayda sətrin hər birində iki tam ədəd $x_i$ ( $1\le x_i\le n$ ) və $y_i$ ( $1\le y_i\le m$ ) – qəpiklərin olduğu xanaların koordinatları verilir. Bütün qəpiklər fərqli xanalarda yerləşir.

Çıxış verilənləri

Çıxışa bir tam ədəd – bütün qəpikləri yığmaq üçün lazım olan günlərin minimum sayını verin.

Nümunələr

Qeyd

Verilmiş nümunədə ərazi:

Oogwayin birinci gün edəcəyi gedişlər aşağıdakı kimi ola bilər:

Oogwayin ikinci gün edəcəyi gedişlər aşağıdakı kimi ola bilər:

Qiymətləndirmə

Bu məsələ aşağıdakı kimi 5 alt tapşırıqdan ibarətdir: