e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Knapsack - Рюкзак

Банкомат

В некотором государстве в обращении находятся банкноты определённых номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен.

Помогите Национальному банку решить задачу.

Входные данные

Первая строка содержит количество номиналов банкнот в обращении n (n100). Вторая строка содержит n различных натуральных чисел x1, x2, ..., xn, не превосходящих 106 - номиналы банкнот. Третья строка содержит сумму s (s106), которую необходимо выдать.

Выходные данные

В первую строку выведите минимальное число слагаемых (или -1, если такого представления не существует). Во вторую строку выведите это представление в любом порядке.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5
1 3 7 12 32
40
Çıxış verilənləri #1
3
32 7 1