Problem C
Brobygge

Rut, som inte har lärt sig simma, vill ta sig över en flod. Som tur är ska en bro byggas över en del av floden, som kan representeras som ett $N \times M$ stort rutnät. Varje timme byggs ett brosegment på en ruta som tidigare var täckt av vatten, så till exempel har fem brosegment byggts efter fem timmar. Rut har fått tag på en lista med positionerna för de första brosegmenten som ska byggas, och hon vet att hon kan ta sig över floden när man kan gå på bron från ena sidan av floden till den andra utan att behöva simma någon sträcka. Hon börjar på rad $0$ och vill ta sig till på rad $N-1$. Dessa två rader har vardera en landmassa som hon kan använda för att gå längs hela floden. Hon kan gå mellan rutor som inte är täckta av vatten genom att gå upp, ner, höger eller vänster. Hon vill nu veta om de givna brosegmenten räcker för att ta sig över, och isåfall hur många timmar hon behöver vänta innan bron är tillräckligt färdig för att kunna ta sig till andra sidan.

 

Figure 1: Illustration av exempelfall 1 efter 4, respektive 7 timmar. Först efter 7 timmar finns en väg till andra sidan.

Indata

Den första raden innehåller tre heltal $N, M$ ($3 \le N, M \le 10^9$), och $T$ ($1 \le T \le 10^5$), antalet rader respektive kolumner i rutnätet och antalet brosegment som ska byggas.

Därefter följer $T$ rader, där den $i$:te raden innehåller två tal $R$ ($1 \le R \le N-2$) och $C$ ($0 \le C \le M-1$), raden och kolumnen där en ruta byggs färdigt på den $i$:te timmen. Notera att i detta problem är rad $0$ raden längst ner.

Utdata

Om Rut kan passera över floden, skriv ut ett heltal: det minsta antalet timmar Rut behöver vänta för att bron ska bli tillräckligt färdig för att kunna gå till andra sidan. Annars, skriv ut "nej".

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

7 3 8
2 1
1 0
4 1
5 1
2 0
3 0
4 0
3 1

7