Účastníci si na LTT vyrábali rôzne plavidlá. Plavidlo vyzerá ako drevený kváder vyplnený sudmi / bandaskami / inými nádobami so vzduchom, aby plavidlo plávalo. Na stavanie potrebujeme najprv vyrobiť rám z dreva. Vedúci na to už dopredu nakúpili kopu materiálu.

Úloha

Máme dostupných $2n$ drevených dosiek a $4n$ drevených hranolov. Každá doska je v tvare obdĺžnika s rozmermi $x$ a $y$. Z týchto vieme postaviť najviac $n$ plavidiel, na každé použijeme dve dosky spojené štyrmi hranolmi do kvádra. Na to aby plavidlo fungovalo musí mať objem aspoň $a$, ale nechceme, aby bolo príliš veľké, teda objem plavidla nesmie byť väčší ako $b$. Dostaneme rozmery dosiek a dĺžky hranolov. Zisti, koľko najviac plavidiel z nich vieme postaviť. Z každej dosky máme dva kusy, a z každého hranolu máme štyri kusy.

Formát vstupu

V prvom riadku vstupu sú tri čísla $n$, $a$ a $b$ ($1 \leq n \leq 10^6$, $1 \leq a \leq b \leq 10^9$) udávajúce počet rôznych dosiek, minimálny objem a maximálny objem plavidla.

V druhom riadku je $n$ čísel $h_i$ ($1 \leq h_i \leq 10^9$) udávajúce dĺžky hranolov.

Nasleduje $n$ riadkov s rozmermi dosiek. V každom riadku sú dve čísla $x$ a $y$ ($1 \leq x, y \leq 10^9$) udávajúce rozmery dosky.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo udávajúce maximálny počet plavidiel, ktoré vieme postaviť z materiálov na vstupe.

Príklady

5 29 35
1 4 3 6 3
10 3
1 8
7 1
6 1
2 5

3

Plavidlá môžu byť napríklad rozmerov $10 \cdot 3 \cdot 1$, $1 \cdot 8 \cdot 4$ a $2 \cdot 5 \cdot 3$. Iné plavidlá s požadovaným objemom vytvoriť nevieme.

3 1 5
1 4 5
10 3
6 1
2 3

0

Najmenšie plavidlá, čo vieme postaviť, májú rozmery $6 \cdot 1 \cdot 1 = 2 \cdot 3 \cdot 1 = 6$, čo už je príliš veľké.