Problem E
Flísar

Stuttu eftir trúskiptin yfir í Kristni er sagt að fyrsti og eini konungur Litháen, Mindaugas, hafi skipað að byggja dómkirkjuna í Vilníus. Byggingin er nánast tilbúin nema gólfið á eftir að þekja skreyttum glansandi postulín flísum.

Gólfið í dómkirkju Vilníus er marghyrningur í tvívíðri sléttu með kartesku hnitakerfi. Marghyrningurinn hefur $N$ mismunandi hornpunkta sem eru númeraðir frá $1$ upp í $N$. Fyrir sérhvert $i$ þar sem $1 \leq i \leq N$ er hornpunktur $i$ staðsettur á punktinum $(X[i], Y[i])$, þar sem $X[i]$ og $Y[i]$ eru ekki neikvæðar heiltölur. Það er brún sem tengir hornpunkt $i$ og hornpunkt $i + 1$ fyrir sérhvert $i$ þar sem $1 \le i \le N-1$ og einnig brún sem tengir hornpunkt $N$ við hornpunkt $1$. Hornpunktarnir eru gefnir annaðhvort í réttsælis röð eða rangsælis röð.

Dómkirkjan er marghyrningur sem er hornréttur á ásana sem þýðir að sérhver brún er samsíða annaðhvort $x$-ásnum eða $y$-ásnum. Enn fremur er dómkirkjan einfaldur marghyrningur, þannig að:

• nákvæmlega tvær brúnir mætast á hverjum hornpunkti;

• sérhvert par af brúnum getur einungis mæst á hornpunkti.

Þau sem eru að byggja dómkirkjuna eiga endalausan fjölda flísa. Hver flís er ferningslaga með hliðarlengd 2. Þau vilja þekja eins stóran hluta dómkirkjunnar eins og mögulegt er. Þá sérstaklega vilja þau velja einhverja lóðrétta línu og þekja hluta dómkirkjunnar sem er vinstra megin við þá línu. Fyrir einhverja heiltölu $k$ látum við $L_ k$ tákna lóðréttu línuna með $x$-hnit jafnt og $k$. Þakning hluta dómkirkjunnar sem er vinstra megin við $L_ k$ er þá úthlutun einhvers fjölda flísa í sléttunni þannig að:

• sérhver punktur sem er innan marghyrningsins og hefur $x$-hnit minna en $k$ er þakinn af einhverri flís;

• enginn punktur sem er utan marghyrningsins eða hefur $x$-hnit meira en $k$ er þakinn af einhverri flís;

• flísarnar skarast ekki.

Minnsta $x$-hnitið af hornpunktunum í dómkirkjunni er $0$. Látum $M$ tákna hæsta $x$-hnit af hornpunktunum í dómkirkjunni.

Verkefni

Hjálpaðu þeim sem byggja dómkirkjuna í Vilníus að ákvarða hæstu heiltölu $k$ þar sem $k \le M$ og það er til þakning af hluta dómkirkjunnar sem er vinstra megin við $L_ k$. Athugaðu að út frá þessarri skilgreiningu er til þakning af hluta dómkirkjunnar sem er vinstra megin við $L_0$ sem notar $0$ flísar.

Inntak

Fyrsta línan af inntakinu inniheldur tvær heiltölur $N$ og $M$ - fjölda hornpunkta og hæsta mögulega $x$-hnit hornpunktanna.

Næst fylgja $N$ línur, þar sem $i$-ta línan samanstendur af tveimur heiltölum $x_ i$ og $y_ i$ sem táknar hnit $i$-ta hornpunktsins. Hornpunktarnir eru gefnir annaðhvort í réttsælis röð eða rangsælis röð.

Úttak

Forritið þitt skal skrifa út hámarksgildið á $k$ þannig að $k \le M$ og það er til þakning fyrir hluta dómkirkjunnar vinstra megin við $L_ k$.

Takmarkanir

• $4 \leq N \leq 2 \cdot 10^5$

• $1 \leq M \leq 10^9$

• $0 \leq y_ i \leq 10^9$ (fyrir sérhvert $1 \leq i \leq N$)

• Dómkirkjan myndar einfaldan marghyrning sem er hornréttur á ásana.

• Minnsta gildið af $x_1, x_2, \dotsc x_ N$ er $0$, og stærsta gildið af $x_1, x_2, \dotsc , x_ N$ er $M$.

Hlutverkefni

Sýnidæmi

1. Eftirfarandi mynd sýnir hluta dómkirkjunnar sem er vinstra megin við línuna $L_ k$ fyrir $k = 2$:

   

   Það er til þakning af hlutanum vinstra megin við $L_2$. Þessi þakning notar tvær flísar.

   Fyrir sérhvert $k > 2$ er ekki til þakning af hluta dómkirkjunnar vinstra megin við $L_ k$.

2. Það er ekkert jákvætt gildi af $k$ þannig það sé til þakning af hluta dómkirkjunnar vinstra megin við $L_ k$.

3. Eins og má sjá á myndinni hér að neðan er hægt að þekja hluta dómkirkjunnar vinstra megin við línuna $L_6$:

   

   Fyrir sérhvert $k > 6$ er ekki til þakning af hluta dómkirkjunnar vinstra megin við $L_ k$.

14 6
0 1
0 3
2 3
2 4
0 4
0 6
3 6
3 7
4 7
6 7
6 5
3 5
3 2
3 1

2

4 3
0 0
0 3
3 3
3 0

0

18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4

6