В городе открылся клуб филателистов, членами которого стремятся стать M человек. На каждом заседании в клуб принимают одного нового филателиста. Чтобы быть принятым, каждый претендент должен предъявить свою коллекцию марок, в которой нет одинаковых экземпляров и которая хоть чем-то отличается от коллекций членов клуба. Для этого каждый новый претендент идет в магазин, где продаются N видов почтовых марок (3 ≤ N ≤ 10000 по ценам X₁ ≤ X₂ ≤ ... ≤ X_N (1 ≤ X_i ≤ 10000, i = 1, ..., N), и покупает соответствующий набор марок, стараясь потратить минимальную сумму денег.

Например, при ассортименте из 5 марок по ценам 3, 4, 6, 10, 15 коллекционеры будут покупать их в представленном ниже порядке:

коллекционер	купленные марки	затраченная сумма денег
первый	1	3
второй	2	4
третий	3	6
четвертый	1 и 2	3+4
пятый	1 и 3	3+6
шестой	4	10
седьмой	2 и 3	4+6
восьмой	1, 2 и 3	3+4+6
девятый	2 и 4	4+10
десятый	5	15
...	...	...

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

Входные данные задаются в файле INPUT.TXT в следующем порядке: в первой строке - N, во второй - M, в последующих N строках указываются цены марок в неубывающем порядке.

Результат решения задачи записывается в файл с именем OUTPUT.TXT. Каждая из M строк этого файла содержит соответствующую искомую сумму затраченных денег для каждого коллекционера. Эти М сумм должны располагаться в неубывающем порядке.

input.txt	output.txt
5 10 3 4 6 10 15	3 4 6 7 9 10 10 13 14 15

• N, M, X_i - натуральные числа, N ≤ M ≤ 2^N-1, M ≤ 15000;
• Тестирование задачи будет осуществляться автоматически, так что никаких отступлений от данного формата ввода/вывода быть не должно;
• Время тестирования не более 30 сек;
• Задача оценивается в 34 балла.