utovar

Na raspolaganju nam je transportno sredstvo cija je nosivost M kilograma (M <= 1000), kao i N vrsta razlicitog tereta (N <= 100) kojeg ima u neogranicenim kolicinama. Ovi tereti su razlicitih težina<br><br>

t1, t2, t3, ... tN<br><br>

i razlicitih vrijednosti<br><br>

v1, v2, v3, ... vN<br><br>

Potrebno je odrediti kolika je najveca moguca ukupna vrijednost tereta koji se može natovariti u transportno sredstvo a da se pri tome ne prekoraci dozvoljena nosivost. Na primjer, uzmimo da je nosivost M = 17, da imamo N = 5 vrsta tereta na raspolaganju sa težinama<br><br>

t1 = 3, t2 = 4, t3 = 7, t4 = 8 i t5 = 13<br><br>

a cije su vrijednosti<br><br>

v1 = 4, v2 = 5, v3 = 10, v4 = 11 i v5 = 13<br><br>

Tada je najveca vrijednost koju možemo ostvariti 24, i to ukoliko uzmemo jedan primjerak prve vrste robe i dva primjerka trece vrste robe. Napomenimo da transportno sredstvo ne mora biti popunjeno do maksimalne nosivosti, tj. u nekim slucajevima može ostati i prazno mjesto (koje je tada sigurno manje od težine najlakšeg tereta).<br><br>

Ulaz:<br>
Ulaz se ucitava sa standardnog ulaza. Prvi red sadrži dva cijela broja, M i N, razdvojena jednim razmakom. Drugi red sadrži N cijelih brojeva ti, i = 1..N koji predstavljaju težine za svaku pojedinu vrstu tereta. Treci red sadrži takoder N cijelih brojeva vi, i = 1..N koji predstavljaju vrijednosti za svaku pojedinu vrstu tereta.<br><br>
Izlaz:<br>
Standardni izlaz treba da sadrži samo jedan red koji sadrži samo jedan cijeli broj koji predstavlja najvecu ukupno mogucu vrijednost tereta (uz poštovanje dozvoljene nosivosti). <br><br>

Primjeri:<br><br>

Ulaz<br>
17 5<br>
3 4 7 8 9<br>
4 5 10 11 13<br><br>
Izlaz<br>
24<br>
<br>
Ulaz<br>
41 3<br>
8 11 12<br>
40 65 78<br>
<br>
Izlaz<br>
236<br>
<br>
Ulaz<br>
55 4<br>
5 8 6 9<br>
3 7 10 8<br>
<br>
Izlaz<br>
90<br>