Algorytmy 2
Dyskretny problem plecakowy
Dany jest zbiór $n$ przedmiotów. Waga $i$-tego z nich, to $w_i$ kilogramów, a wartość - $c_i$ złotych. Złodziej jest w stanie unieść co najwyżej $b$ kilogramów. Pomóż mu wybrać przedmioty tak, aby jego zysk był możliwie jak największy. Przedmiotów nie można dzielić na kawałki. Każdy przedmiot można wziąć co najwyżej raz.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby:
$n$ i $b$ - liczbę przedmiotów i ograniczenie na wagę.
Drugi wiersz zawiera $n$ liczb $w_i$ - wagi przedmiotów.
Trzeci wiersz zawiera $n$ liczb $c_i$ - wartości przedmiotów.
Wyjście
Pierwszy i jedyny wiersz wyjścia zawiara jedną liczbę, maksymalny zysk złodzieja.
Ograniczenia
- $1 \le n \le 1000$
- $1 \le b \le 10^5$
- $1 \le w_i, c_i \le 1000$
Przykłady
Wejście 1
4 10
4 8 5 3
5 12 8 1
Wyjście 1
13