Zadanie: Banknoty
Bajtocki Bank Bitowy (w skrócie BBB) ma największą w Bajtocji sieć
bankomatów.
BBB postanowił usprawnić swoje bankomaty i zwrócił się do Ciebie
o pomoc.
Środkiem płatniczym w Bajtocji są banknoty o nominałach
b1, b2,..., bn.
BBB postanowił, że bankomaty powinny wypłacać żądaną kwotę
w jak najmniejszej łącznej liczbie banknotów.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis zapasu banknotów, które
posiada bankomat, oraz kwotę do wypłacenia,
- obliczy minimalną łączną liczbę banknotów, za pomocą jakiej
bankomat może wypłacić żądaną kwotę, oraz znajdzie pewien sposób
jej wypłacenia,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się liczba
nominałów n,
1 <= n <= 200.
Drugi wiersz zawiera n liczb całkowitych
b1, b2,..., bn,
1 <= b1 < b2 < ... < b n <= 20 000,
pooddzielanych pojedynczymi odstępami.
Trzeci wiersz zawiera n liczb całkowitych
c1, c2,..., cn,
1 <= ci <= 20 000,
pooddzielanych pojedynczymi odstępami; ci jest liczbą
banknotów o nominale bi znajdujących się w bankomacie.
W ostatnim, czwartym wierszu wejścia znajduje się jedna liczba
całkowita k -- kwota, którą bankomat ma wypłacić,
1 <= k <= 20 000.
Możesz założyć, dla danych testowych, że kwotę k można
wypłacić za pomocą dostępnych banknotów.
Wyjście
Pierwszy wiersz wyjścia powinien zawierać jedną dodatnią liczbę
całkowitą równą minimalnej łącznej liczbie banknotów,
za pomocą których bankomat może wypłacić kwotę k.
Drugi wiersz wyjścia powinien zawierać n liczb całkowitych,
oddzielonych pojedynczymi odstępami i oznaczających liczby sztuk
poszczególnych banknotów użytych do wypłacenia kwoty k.
W przypadku, gdy istnieje więcej niż jedno rozwiązanie, program
powinien wypisać którekolwiek.