Master Oogway#10673

Master Oogway

0,5 saniyə

64 meqabayt

Çox asan

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üş $n x m$ ö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 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^{9} ) və $m$ ( $1 \leq m \leq 1 0^{9}$ 1 \leq m \leq 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 \leq q \leq 1 0^{5}$ 1 \leq q \leq 10^{5} ) – qəpiklərin sayı. Növbəti $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \leq q \leq 10^{5} ) sayda sətrin hər birində iki tam ədəd $x_{i}$ x_i ( $1 \leq x_{i} \leq n$ 1 \leq x_i \leq n ) və $y_{i}$ y_i ( $1 \leq y_{i} \leq m$ 1 \leq y_i \leq m ) – qəpiklərin olduğu xanaların koordinatları verilir. Bütün qəpiklər fərqli xanalarda yerləşir.