e-olymp
Competitions

Knapsack - Рюкзак

ATM

In some country in circulation there are notes of certain denominations. National Bank wants the cash machine to give out any requested amount with a minimum number of banknotes, considering that the amount of banknotes of each denomination is unlimited.

Help the National Bank to solve this problem.

Input

First line contains the number of banknotes denominations in circulation n (n100). Second line contains n different positive integers x1, x2, ..., xn not greater than 106 - the banknotes denominations. Third line contains the sum s (s106) that you want to give.

Output

Print in the first line the minimal number of summands (or -1 if such representation does not exist). In the second line print these summands in any order.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
5
1 3 7 12 32
40
Output example #1
3
32 7 1