eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Банкомат

Банкомат

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Допоможіть Національному Банку розв'язати задачу.

Вхідні дані

Перший рядок містить кількість номіналів банкнот n(n ≤ 100) в обороті. Другий рядок містить n різних натуральних чисел x_1, x_2, ..., x_N, які не перевищують 10^6 - номінали банкнот. Третій рядок містить суму s(s ≤ 10^6), яку необхідно видати.

Вихідні дані

У перший рядок виведіть мінімальну кількість доданків (або -1, якщо такого подання не існує). У другий рядок виведіть це подання у довільному порядку.

Приклад

Вхідні дані #1
5
1 3 7 12 32
40
Вихідні дані #1
3
32 7 1