Jäätelö |
| Time limit: | 1.00 s |
| Memory limit: | 512 MB |
|
Uolevi aikoo ostaa kaksi jäätelötötteröä: yhden Maijalle ja yhden itselleen. Tiedossasi on jokaisen myynnissä olevan jäätelötötterön hinta ja paino sekä suurin summa, jonka Uolevi voi käyttää ostokseen.
Tehtäväsi on selvittää, mikä on suurin mahdollinen jäätelötötteröiden yhteispaino. Huomaa, että Uolevi voi ostaa myös kaksi samanlaista jäätelötötteröä.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $x$: vaihtoehtojen määrä ja Uolevin rahamäärä.
Sitten syötteessä on $n$ riviä, joista jokainen kuvaa yhden vaihtoehdon. Rivillä on kaksi kokonaislukua $h$ ja $p$: jäätelötötterön hinta ja paino.
Voit olettaa, että on olemassa ainakin yksi ratkaisu.
Tuloste
Tulosta yksi kokonaisluku: suurin mahdollinen yhteispaino.
Esimerkki 1
Syöte:
3 10
1 1
5 4
9 8
Tuloste:
9
Selitys: Uolevi ostaa 1-hintaisen ja 9-hintaisen jäätelötötterön.
Esimerkki 2
Syöte:
2 7
4 2
3 5
Tuloste:
10
Selitys: Uolevi ostaa kaksi 3-hintaista jäätelötötteröä.
Rajat
- $1 \le n \le 100$
- $1 \le x,h,p \le 1000$
Pisteytys
Saat tehtävästä 100 pistettä, jos ohjelmasi tuottaa oikean vastauksen kaikkiin testisyötteisiin, ja muuten 0 pistettä.
