Annettuna on $n$ tavaraa, joista on tiedossa paino, arvo ja määrä.

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

Syöte

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

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

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

Lopuksi syötteessä on $n$ kokonaislukua $m_1,m_2,\ldots,m_n$: tavaroiden määrät.

Tuloste

Tulosta suurin mahdollinen tavaroiden yhteisarvo.

Rajat

• $1 \le n \le 1000$
• $1 \le x \le 5000$
• $1 \le p_i,a_i \le 100$
• $1 \le m_i \le 5000$

Esimerkki

Syöte:

3 10
2 5 2
2 4 3
3 1 2

Tuloste:

12