eolymp
Змагання

9 витків спіралі. Виток 3. Крок 5.

Банкомат

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

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

Вхідні дані

Перший рядок містить кількість номіналів банкнот n (n100) в обороті. Другий рядок містить n різних натуральних чисел x1, x2, ..., xN, які не перевищують 106 - номінали банкнот. Третій рядок містить суму s (s106), яку необхідно видати.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
1 3 7 12 32
40
Вихідні дані #1
3
32 7 1