CSES - Antikvariaatti II
  • Time limit: 1.00 s
  • Memory limit: 128 MB
Olet antikvariaatissa, jossa on myynnissä $n$ erilaista kirjaa. Tiedät jokaisesta kirjasta hinnan, sivumäärän sekä montako kappaletta kirjaa on myynnissä.

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

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $x$: kirjojen määrä ja suurin sallittu kokonaishinta.

Seuraavalla rivillä on $n$ lukua $h_1,h_2,\ldots,h_n$: kunkin kirjan hinta.

Seuraavalla rivillä on $n$ lukua $s_1,s_2,\ldots,s_n$: kunkin kirjan sivumäärä.

Viimeisellä rivillä on $n$ lukua $k_1,k_2,\ldots,k_n$: kunkin kirjan kappalemäärä.

Tuloste

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

Rajat
  • $1 \le n \le 100$
  • $1 \le x \le 10^5$
  • $1 \le h_i, s_i, k_i \le 1000$
Esimerkki

Syöte:
3 10
2 6 3
8 5 4
3 5 2


Tuloste:
28

Selitys: Ostat kolme kappaletta kirjaa 1 ja yhden kappaleen kirjaa 3. Hinta on $3 \cdot 2 + 3 = 9$ ja sivumäärä on $3 \cdot 8 + 4 = 28$.