Predstavte si, že ste lupič. Vlámali ste sa do múzea a máte k dispozícii batoh s obmedzenou nosnosťou $w$. Pred vami leží hromada $n$ umeleckých diel a artefaktov. Každý predmet má svoju váhu $w_i$ a určitú vzácnosť $v_i$.
Vašou úlohou je vybrať si z týchto predmetov takú kombináciu, ktorá sa vám zmestí do batohu (t.j., ich celková váha neprekročí nosnosť batohu) a zároveň vám prinesie čo najvyššiu celkovú vzácnosť.
Nemôžete vziať len časť predmetu – buď ho vezmete celý, alebo vôbec.
Na prvom riadku vstupu sa nachádzajú dve čísla - $n$ (počet predmetov v múzeu) a $W$ (nosnosť vášho batohu).
Na druhom riadku vstupu sa nachádza $n$ medzerou oddelených čísiel, ktoré reprezentujú váhy jednotlivých predmetov $w_i$.
Na treťom riadku vstupu sa nachádza $n$ medzerou oddelených čisiel, ktoré reprezentujú vzácnosti jednotlivých predmetov $v_i$.
Na jedinom riadku výstupu vypíšte jedno číslo -- najväčšiu možnú vzácnosť predmetov, ktorá sa vám zmestí do batohu.
4 6
4 3 2 1
5 4 3 2
9