Problem G
Eldur

Á gamla Eystrasaltssvæðinu, þá er mikilvægt að hafa heilagan eld í bruna. Prestur, kallaður krivis, er ábyrgur fyrir því að ekki slokkni á eldinum. Hann hefur marga trausta aðstoðarmenn, kallaðir vaidilutė, og langar hann að búa til áætlun fyrir þá til að vernda eldinn. Hann þarf að passa upp á að eldurinn er alltaf vaktaður af einhverjum vaidilutė.

Krivis notar sitt eigið tímamælingarkerfi, þar sem hver dagur er $M$ mínútur. Það eru $N$ vaidilutė í þorpinu. Vaidilutė númer $i$ hefur möguleika að vinna á tímabilinu sem er lýst með tveimur heiltölum $s_i$ og $e_i$. Tíminn $s_i$ táknar fyrsta tíma dags sem hún getur unnið og $e_i$ táknar síðasta tíma dags sem hún getur unnið. Tími er talinn í mínútum frá byrjun hvers dags. Takið eftir því að þegar $s_i>e_i$, þá er vaidilutė tilbúinn að vinna yfir nóttina.

Krivis biður þig að velja einhverjar vaidilutė og raða þeim niður á vaktir. Hver valin vaidilutė þarf að byrja vaktina sína í fyrsta lagi á tíma $s_i$, og enda hana í síðasta lagi á tíma $e_i$. Hver vakt er alltaf styttri en heill dagur. Hver valin vaidilutė endurtekur vaktina sína á hverjum degi.

Þegar vaktaskipti eiga sér stað á milli vaidilutė þá aukast líkurnar að það slokkni á eldinum. Út af því, þá viltu lágmarka fjöldann sem vaktaskipti eiga sér stað á hverjum degi og búa til áætlun sem lágmarkar fjölda vaidilutė.

Verkefni

Reiknaðu lágmarksfjölda af vaidilutė sem þarf að velja, þannig að það sé alltaf einhver að vakta heilaga eldinn.

Inntak

Fyrsta línan inniheldur tvær heiltölur $N$ og $M$ - fjöldi vaidilutė og lengd dagsins í mínútum.

Næst fylgja $N$ línur, þar sem lína $i$ inniheldur tvær heiltölur $s_i$ og $e_i$ – fyrsta upphafstíma og síðasta lokatíma fyrir vaidilutė númer $i$.

Úttak

Skrifið út eina heiltölu - lægsta fjölda vaidilutė sem þarf að velja. Ef það er ómögulegt að velja vaidilutė samkvæmt kröfum, þá skal skrifa út $-1$.

Takmarkanir

• $1\le N\le 2\cdot {10}^5$

• $2\le M\le {10}^9$

• $0\le s_i,e_i<M$ (fyrir öll $1\le i\le N$)

• $s_i\ne e_i$ (fyrir öll $1\le i\le N$)

Hlutverkefni

Sýnidæmi

Í fyrsta sýnidæminu getur þú valið fyrstu, aðra og fjórðu vaidilutė og raðað vöktum þeirra á eftirfarandi hátt

• Fyrsta vaidilutė vinnur frá 10 mínútu að 30 mínútu.

• Önnur vaidilutė vinnur frá 30 mínútu að 70 mínútu.

• Fjórða vaidilutė vinnur frá 70 mínútu að 10 mínútu næsta dags.

Í öðru sýnidæminu er ómögulegt að velja áætlun þar sem það er einungis ein vaidilutė og hún getur ekki unnið allan daginn.

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1