3. Intraplanetárne čížmy

Jožko Číž už dlhé roky prebýva na istej planétke. Zo začiatku sa mu všetko zdalo zaujímavé a bol celý nadšený. Časom však nadšenie opadlo a začínal sa trochu nudiť. Planétka má slabú gravitáciu a dobre sa tu skáče. To však Číž už dobre pozná. Tentoraz však uvidel čížmy. Nie obyčajné čížmy. Vesmírne skákacie čížmy! Pozrel sa ďalej a uvdiel ďalšie. A ďalšie. A ďalšie! Videl celú cestu, na ktorej bolo veľa rôznych skákacích čížiem.

Rozhodol sa, že sa vydá na túru na koniec tejto cesty. Samozrejme sa mu nechce chodiť a prezúvať čížmy po tom, čo sa vybijú, je pre energeticky úsporného Číža neprípustné. S každými čížmami dokáže preskákať inú vzdialenosť dokedy sa vybijú. Zaujímalo by ho, koľko najmenejkrát sa musí prezuť na to, aby sa dostal na koniec cesty.

Úloha

Máme cestu danej dĺžky na ktorej začiatku sa nachádza Číž. Na niektorých pozíciách cesty sú čížmy, do ktorých sa môže Číž prezuť, ak je na ich pozícii. Každé čížmy majú inú vzdialenosť, ktorú je nimi možné preskákať. Vašou úlohou je zistiť, koľko najmenej krát musí čížmy prezuť aby sa dostal na koniec cesty, bez toho aby chodil, alebo zistiť, že to možné nie je.

Formát vstupu

V prvom riadku sú tri celé čísla \(n, d, b\). Číslo \(n (1 \leq n \leq 500\,000)\) udáva počet čížiem na ceste. Číslo \(d (2 \leq d \leq 10^9)\) udáva dĺžku cesty a \(b (1 \leq b \leq 10^9)\) udáva vzdialenosť ktorú je možné prejsť s čížmami, ktoré má Číž už obuté.

Následuje \(n\) riadkov popisujúcich čížmy na ceste. Na i-tom riadku, sú celé čísla \(A_i (1 \leq A_i < d)\) a \(B_i (1 \leq B_i \leq 10^9)\) popisujúce pozíciu čížiem na ceste a vzdialenosť ktorú je s nimi možné prejsť.

Je zaručené, že hodnoty \(A_i\) sú zoradené vzostupne. Teda čížmy sú vypísané postupne v poradí, ako sa nachádzajú na ceste. Na jednej pozícii sa tiež nachádzajú vždy najviac jedny čízmy.

V jednotlivých sadách platia aj následujúce obmedzenia pre \(n\):

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo. Najmenší možný počet prezutí čížiem potrebný na prejdenie na koniec cesty. Ak cestu nie je možné prejsť pomocou čížiem, vypíšte \(-1\).

Príklady

Input:

5 20 1
1 2
2 4
3 1
5 16
7 20

Output:

3

Musíme zobrať prvé čížmy a následne sa najviac oplatia druhé. Potom vieme zobrať štvrté (na pozícii 5), s ktorými sa vieme dostať až na koniec cesty.

Input:

4 10 2
1 2
2 2
6 4
8 1

Output:

-1

Síce vieme zobrať prvé, alebo druhé čížmy, ale potom sa už k ďalším nevieme dostať a ani dôjsť na koniec cesty. Odpoveď je teda \(-1\).