CSES - Antikvariaatti
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Olet antikvariaatissa, jossa on myynnissä yhteensä nn kirjaa. Tiedät jokaisen kirjan hinnan ja sivumäärän.

Olet päättänyt, että ostostesi kokonaishinta saa olla enintään xx. Montako sivua lukemista voit ostaa enintään?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja xx: kirjojen määrä ja suurin sallittu kokonaishinta.

Seuraavalla rivillä on nn lukua h1,h2,,hnh_1,h_2,\ldots,h_n: kunkin kirjan hinta.

Viimeisellä rivillä on nn lukua s1,s2,,sns_1,s_2,\ldots,s_n: kunkin kirjan sivumäärä.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen sivumäärä.

Rajat

  • 1n10001 \le n \le 1000
  • 1x1051 \le x \le 10^5
  • 1hi,si10001 \le h_i, s_i \le 1000

Esimerkki

Syöte:

4 10
4 8 5 3
5 12 8 1

Tuloste:

13

Selitys: Ostat kirjat 1 ja 3. Niiden hinta on 4+5=94+5=9 ja sivumäärä on 5+8=135+8=13.