Annettuna on n tavaraa, joista on tiedossa paino ja arvo.

Tehtäväsi on pakata reppuun tavaroita niin, että niiden yhteispaino on enintään x ja yhteisarvo on mahdollisimman suuri.

Syöte

Syötteen ensimmäisellä rivillä kaksi kokonaislukua n ja x: tavaroiden määrä ja suurin sallittu yhteispaino.

Sitten syötteessä on n kokonaislukua p_1,p_2,\ldots,p_n: tavaroiden painot.

Lopuksi syötteessä on n kokonaislukua a_1,a_2,\ldots,a_n: tavaroiden arvot.

Tuloste

Tulosta suurin mahdollinen tavaroiden yhteisarvo.

Rajat

• 1 \le n \le 500
• 1 \le x \le 10^6
• 1 \le p_i \le 1000
• 1 \le a_i \le 10

Esimerkki

Syöte:

3 5
2 5 2
2 4 3

Tuloste:

5