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

Olet antikvariaatissa, jossa on myynnissä nn 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 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.

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

Viimeisellä rivillä on nn lukua k1,k2,,knk_1,k_2,\ldots,k_n: kunkin kirjan kappalemäärä.

Tuloste

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

Rajat

  • 1n1001 \le n \le 100
  • 1x1051 \le x \le 10^5
  • 1hi,si,ki10001 \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 32+3=93 \cdot 2 + 3 = 9 ja sivumäärä on 38+4=283 \cdot 8 + 4 = 28.