Вор пробрался в магазин.
Как всегда у него с собой любимый рюкзак. В рюкзаке может поместиться k предметов. В магазине присутствует n типов товаров, причём товаров каждого типа бесконечное количество. Стоимость единицы товара i-го типа равна ai.
Вор жадный, поэтому решил набить рюкзак до отказа. Таким образом, он возьмёт с собой ровно k товаров, причём товары некоторых типов он может взять в нескольких экземплярах.
Определите всевозможные суммы стоимостей товаров, которые могут оказаться в рюкзаке вора.
Выходные данные
В единственной строке выведите через пробел всевозможные суммы стоимостей товаров, которые могут оказаться в рюкзаке вора. Числа нужно выводить в порядке возрастания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 3
|
2 3 4 5 6
|
|
2
|
5 5
1 1 1 1 1
|
5
|
|
3
|
3 3
3 5 11
|
9 11 13 15 17 19 21 25 27 33
|