Code Submission Evaluation System Login

IOI-leiri 2016

Repunpakkaus II


Task | Statistics


CSES - Repunpakkaus IICSES - Repunpakkaus II

Time limit:1.00 s Memory limit:128 MB

Annettuna on $n$ tavaroita, 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
Esimerkki

Syöte:
3 5
2 5 2
2 4 3


Tuloste:
5