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.