Utovar

Opis zadatka:

Na raspolaganju nam je transportno sredstvo čija je nosivost M kilograma (M <= 1000), kao i N vrsta različitog tereta (N <= 100) kojeg ima u neograničenim količinama. Ovi tereti su različitih težina

t₁, t₂, t₃, ... t_N

i različitih vrijednosti

v₁, v₂, v₃, ... v_N

Potrebno je odrediti kolika je najveća moguća ukupna vrijednost tereta koji se može natovariti u transportno sredstvo a da se pri tome ne prekorači dozvoljena nosivost. Na primjer, uzmimo da je nosivost M = 17, da imamo N = 5 vrsta tereta na raspolaganju sa težinama

t₁ = 3, t₂ = 4, t₃ = 7, t₄ = 8 i t₅ = 13

a čije su vrijednosti

v₁ = 4, v₂ = 5, v₃ = 10, v₄ = 11 i v₅ = 13

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

Izvršni program mora imati naziv UTOVAR.EXE.

Ulazna datoteka:

Ulazna datoteka UTOVAR.IN koja se nalazi u tekućem direktoriju ima tri reda. Prvi red sadrži dva cijela broja, M i N, razdvojena jednim razmakom. Drugi red sadrži N cijelih brojeva t_i, i = 1..N koji predstavljaju težine za svaku pojedinu vrstu tereta. Treći red sadrži također N cijelih brojeva v_i, i = 1..N koji predstavljaju vrijednosti za svaku pojedinu vrstu tereta.

Izlazna datoteka:

Program treba da kreira izlaznu datoteku UTOVAR.OUT u tekućem direktoriju. Datoteka treba da sadrži samo jedan red koji sadrži samo jedan cijeli broj koji predstavlja najveću ukupno moguću vrijednost tereta (uz poštovanje dozvoljene nosivosti). Na kraju reda ne treba stajati oznaka kraja reda (EOL marker).

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.

Primjeri:

UTOVAR.IN
17 5
3 4 7 8 9
4 5 10 11 13
UTOVAR.OUT
24
UTOVAR.IN
41 3
8 11 12
40 65 78
UTOVAR.OUT
236
UTOVAR.IN
55 4
5 8 6 9
3 7 10 8
UTOVAR.OUT
90

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]