Kapitan Mambeks wybrał się na cotygodniowe zakupy. Po otrzymaniu rachunku przy kasie zaczął się długo zastanawiać. Fakt ten zirytował kasjerkę, która w końcu zapytała go, dlaczego nie płaci za towar. Kapitan ze spokojem odparł, że zastanawia się jaka jest minimalna liczba banknotów potrzebnych do tego, aby zapłacić za zakupiony towar. Kapitan oczywiście miał tu na myśli każdy banknot jaki on da kasjerce, ale także każdy banknot jaki otrzyma od kasjerki.
Zarówno kapitan jak i kasjerka dysponują nieograniczoną liczbą banknotów każdego nominału. Niech przykładowo kwota do zapłaty wynosi 800, a dostępnymi banknotami będą banknoty o nominałach 100 i 1000. Aby zapłacić za towar potrzebne są trzy banknoty: banknot o nominale 1000, który kapitan da kasjerce oraz dwa banknoty o nominale 100, które kapitan otrzyma od kasjerki.
Twoim zadaniem jest napisanie programu, który wyznaczy jaka jest minimalna liczba banknotów potrzebnych do zapłacenia za zakupiony towar.
Dane wejściowe składają się z K+1 wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i składa się on z sekwencji liczb całkowitych oddzielonych spacją. Pierwsza liczba w wierszu zawiera kwotę do zapłaty, która jest dodatnia i nie przekracza 50000. Kolejne liczby określają nominały dostępnych banknotów (każda liczba jest różna). Maksymalna liczba nominałów nie przekracza 1000, a nominał banknotu nie przekracza 10000. Ostatnią wartością w wierszu jest liczba 0, która oznacza koniec pojedynczego zestawu danych.
Dane wejściowe zakończone są wierszem zawierającym pojedynczą liczbę 0.
Dane wyjściowe składają się z K wierszy. Jeden wiersz odpowiada pojedynczemu zestawowi danych i zawiera minimalną liczbę banknotów potrzebnych do zapłacenia za towar, lub liczbę -1 w przypadku kiedy nie ma możliwości zapłaty za towar dysponowanymi banknotami.
800 1000 100 0 253 200 50 25 30 0 8 3 7 0 5 7 3 0 21 2 4 6 8 10 0 0
3 -1 4 5 -1