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ä.