Book of programming problems

Complexity (1-100): 20

A new philately club is open, and M philatelists are striving to become its members. At each meeting, the club takes only one member on. In order to become a member, a philatelist must demonstrate that his or her collection of stamps does not contain the same stamp twice and is different from collections of other members. Each philatelist therefore buys a collection of stamps, trying to spend as little money as possible, at the post stamp shop, offering N kinds of stamps (3≤N≤10000) priced x₁,x₂,...,x_n respectively (3≤x_i≤10000, i=1 .. N).

For example, if the shop offers 5 kinds of stamps which cost 3, 4, 6, 10, 15, the philatelists will buy them in the following order:

Philatelist	Stamps bought	Money spent
1	1	3
2	2	4
3	3	6
4	1 and 2	3+4
5	1 and 3	3+6
6	4	10
7	2 and 3	4+6
8	1,2, and 3	3+4+6
9	1 and 4	3+10
10	2 and 4	4+10
. . .

Write a program which, based on stamp prices, would calculate the minimum amount of money each philatelist should spend to become a philately club member.

The input data should be read from a text file, containing numbers in separate lines in the following order: the first line id N, the second is M, the next N lines contain stamp prices in ascending order. The output should contain amount of money for each of M philatelists, in ascending order.

Note: All numbers are natural, N≤ M≤2^N-1, M≤15000. The program is allowed to run no longer than 3 seconds.
Self-tests: self-test 1, self-test 2