1. Lúka neštastia vzorové riešenie

Pastier Larry má problém. Kolmo cez pasienku kde sa pasú jeho ovečky prechádza prekliata rieka nekonečného zatratenia a bolesti. Ovečku, ktorá by do nej omylom padla čaká neistý ale nepredstaviteľne mrzký osud. Navyše strata akejkoľvek ovečky prináša pre chudobného pastiera značnú ekonomickú škodu. Larry má ale nápad ako túto hrozbu mitigovať.

V stodole má k dispozícii niekoľko veľkých obdĺžnikových oceľových plátov. Pripevní ich cez rieku, aby po nich mohli ovečky bezpečne prechádzať na druhú stranu. Pasienka má členitý terén a rieka má nerovné brehy, takže pláty nemôže namontovať kam len chce, ale našiel nejaké potenciálne miesta kde sa to dá. Všetky majú rovnakú veľkosť a otočenie (sú rovnobežné s riekou).

Čím viac plátov pastier Larry rozmiestni, tým menej ovečiek stratí. Ale pláty sa nesmú prekrývať, aby sa nenarušila ich stabilita. Poraďte pastierovi Larryho, koľko najviac plátov môže cez rieku pripevniť.

Úloha

Pôdorys pasienky je nekonečná 2D rovina. Rieku si môžeme predstaviť ako priamku \(y=0\).¹ Na pasienke je \(n\) osovo zarovnaných obdĺžnikov, čo sú miesta kde Larry môže potenciálne umiestniť plát. Všetky majú rovnakú šírku \(s\) a výšku \(v\) a pretínajú rieku.

Vyber na ktoré miesta má Larry namontovať oceľový plát a na ktoré nie, tak aby ich bolo čo najviac ale žiadne vybraté miesta sa neprekrývali. Dotýkať sa môžu.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet potenciálnych obdĺžnikov.

V druhom riadku je prirodzené číslo \(s\) a v treťom riadku prirodzené číslo \(v\), určujúce šírku a výšku každého obdĺžnika.

Nasleduje \(n\) riadkov ktoré popisujú jednotlivé potenciálne miesta. V každom sú dve celé čísla \(x\) a \(y\), čo predstavuje obdĺžnik ktorého štyri rohy sú \((x,y)\), \((x+s,y)\), \((x,y+v)\) a \((x+s,y+v)\). Všetky obdĺžniky pretínajú rieku, čiže \(y < 0 < y+v\). Všetky obdĺžniky na vstupe sú navzájom rôzne. Obdĺžniky sú zoradené vzostupne podľa ich \(x\)-ovej súradnice. Ak majú viaceré rovnaké \(x\), môžu byť medzi sebou zoradené akokoľvek.

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Formát výstupu

Vypíš jedno číslo: veľkost najväčšej podmnožiny vzájomne sa neprekryvajúcich obdĺžnikov.

Príklady

Input:

4
2
5
-5 -4
-4 -3
-1 -1
1 -2

Output:

3

Prvé 2 obdĺžniky sa prekrývajú, preto musíme vybrať práve jeden z nich. Je jedno ktorý. Ostatné sa s nijakým obdĺžnikom neprekrývajú, iba dotýkajú, takže ich vyberieme oba. Maximum je teda 3.