3. Asteroidné T-rexy útočia

Bol obyčajný pondelkový večer. Ralbo sa spokojne pozeral na hviezdne kravy ako sa pomaličky šinuli do svojho chlieva. Keď vtom počul z rozhlasu:

“VYHLASUJEM POPLACH! VYHLASUJEM POPLACH! ASTEROIDNÉ T-REXY ÚTOČIA!”

“Do kelu!” vykĺzlo Ralbovi z úst. “Cvalom do chlieva!” zakričal Ralbo. Kravy, keď to začuli, tak sa plnou rýchlosťou rozbehli do chlieva. Keďže sú to veľmi velké zvieratá, tak doňho museli chodiť za sebou a nemohli sa predbiehať. Bohužial, nie všetky bežia rovnako rýchlo a Ralbovi bolo na prvý pohľad jasné, že niektoré to nezvládnu. “Musím ich zachrániť aspoň toľko, aby bolo dosť jedla pre stanicu na ďalší mesiac.” Ralbo teda hneď dobehol do žeriavu, ktorý bol nachystaný hneď vedľa a dal sa do dvíhania pomalých kráv.

Ten žeriav je ale veľmi starý, takže ho Ralbo chce používať čo najmenej.

Koľkokrát musí použiť ten starý žeriav, aby zachránil dosť kráv?

Úloha

Vieme počet kráv, ktoré treba stanici na mesiac, koľko času zostáva do príchodu asteroidných t-rexov, akou rýchlosťou bežia kravy a ako ďaleko sú od chlieva. Vašou úlohou je zistiť, najmenej koľkokrát treba použiť žeriav, aby prešlo dosť kráv, aby mala stanica jedlo na mesiac.

Žeriav sa používa tak, že Ralbo na chvíľu zoberie jednu kravu do vzduchu, nechá práve jednu kravu, aby pod ňou prebehla a potom ju znova položí. Žeriav pracuje a presúva sa instantne (trvá to 0 času).

Kravy sú veľmi veľké a nevedia prejsť okolo seba na ceste do chlieva a musia bežať za sebou. Ak rýchlejšia krava narazí na pomalšiu cestou do chlieva, tak bude bežať jej rýchlosťou a dorazia do chlieva naraz. Ak krava príde do chlieva presne vtedy, keď prídu asteroidné t-rexy, tak sa jej podarí ujsť.

Formát vstupu

Na vstupe najskôr dostaneme 3 čísla - počet kráv \(n\), čas do príchodu t-rexov \(t\) a počet kráv, ktoré potrebuje základňa na prežitie \(p\).

Potom dostaneme \(n\) riadkov s dvomi číslami. Na \(i\)-tom riadku budú čísla \(s_i, v_i\) - vzdialenosť \(i\)-tej kravy a jej rýchlosť. Vzdialenosti kráv od chlieva sú rastúce.

Platia nasledovné obmedzenia:

Formát výstupu

Na výstup vypíšte jedno číslo - počet zdvihnutí, alebo -1, ak nie je možné dvíhať kravy tak, aby bolo dosť jedla pre základňu

Príklad

Input:

4 3 3
1 5
2 1
4 1
10 10

Output:

1

Stačí, aby Ralbo zodvihol predposlednú kravu, keď ju dobehne posledná krava

Input:

5 1 1
2 1
3 2
5 3
6 1
9 8

Output:

-1

Žiadna krava nestihne dobehnúť do chlieva, nech ich Ralbo zdvíha ľubovoľne

Input:

5 1 1
2 1
3 1
4 1
5 1
6 9

Output:

4

Iba posledná krava stihne dôjsť do cieľa. Ralbo musí zodvihnúť všetky pred ňou