Sesja

Dysponujemy nieograniczonym zbiorem nominałów. Naszym zadaniem jest napisanie programu, który wyda określoną resztę jak najmniejszą liczbą nominałów.

Wejście:

Na wejściu podajemy liczbę powtórzeń serii danych. W następnym wierszu wpisujemy liczbę nominałów, a następnie w kolejnych wierszach nominały będące liczbami całkowitymi dodatnimi niewiększymi niż 1000. W ostatnim wierszu podajemy liczbę całkowitą dodatnią - resztę do wydania.

Wyjście:

Na wyjściu dostajemy najmniejszą liczbę nominałów n<4000 potrzebną do wydania reszty lub informację niemożliwe zakończone znakiem nowej linii.

Przykład
Wejście:
2
2
3
5
17
2
10
100
1050
Wyjście
niemożliwe
15

Wskazówka:
Zastosować algorytm dynamiczny. Zachłanny nie zawsze jest poprawny.