Vitaminai

문제

Žiemos laikotarpiu svarbu pasirūpinti, kad organizmas gautų pakankamai vitaminų. Adomas, tą suprasdamas, užėjo į vaistinę „Vitaminų Pasaulis“. Ši vaistinė parduoda įvairiausias multivitaminų tabletes. Kadangi nesaikingai vartojant vitaminus galima pakenkti, vaistinė vienam pirkėjui parduoda ne daugiau kaip vieną tos pačios rūšies tabletę.

Adomą labiausiai domina vitaminas C, kuris stiprina imunitetą, ir vitaminas D, kuris labai svarbus kaulams ir dantims. Tačiau parduotuvė turi tiek daug įvairių tablečių, kad Adomas pasimetė.

Žinoma koks kiekis vitamino C ir vitamino D yra kiekvienoje tabletėje, bei nurodyta kiekvienos tabletės kaina. Raskite, kiek mažiausiai turės sumokėti Adomas, kad įsigytų bent $CC$ miligramų vitamino C ir bent $DD$ miligramų vitamino D.

입력

Pirmojoje eilutėje įrašyti trys sveikieji skaičiai: tablečių skaičius $NN$ ir Adomo norimas vitaminų kiekis $CC$ ir $DD$.

Tolimesnėse $NN$ eilučių aprašytos tabletės. Kiekvienoje eilutėje įrašytas vitamino $CC$ kiekis $c_{i}c\_i$, vitamino $DD$ kiekis $d_{i}d\_i$ (miligramais), ir tabletės kaina centais $k_{i}k\_i$. Visi skaičiai yra sveikieji.

출력

Pirmojoje eilutėje išveskite vieną sveikąjį skaičių: kiek mažiausiai centų turės išleisti Adomas, kad įsigytų bent $CC$ miligramų vitamino C, ir bent $DD$ miligramų vitamino D.

Sprendinys visada egzistuos: nusipirkęs visas tabletes, Adomas visuomet gaus norimą kiekį vitaminų.

5 300 50
100 30 50
200 10 25
100 50 100
400 0 80
0 100 200

125