2 X 1 P96199

Ivan and his n−1 friends (a total of n freaks) are about to have dinner. As they enter the restaurant they see a big sign that says

After everyone has decided what he wants to eat (one or more dishes), they start wondering what is the minimum total price that they can achieve. They must decide the following:

1. Who should order what.
2. Who should be whose companion, so that the offer can be applied on each pair.

As long as every dish is ordered by someone, it does not matter by who (dishes can be rearranged after the waiter brings them to the table). There is no upper limit on the number of dishes that a single person can order. Also, having someone not ordering anything is perfectly fine.

For instance, if five people p₁, p₂, p₃, p₄ and p₅ want six dishes with prices 10, 15, 20, 23, 30 and 42, then an optimal solution is to have p₁ not ordering anything, p₂ ordering 10 and 20, p₃ ordering 30, p₄ ordering 15 and 23, p₅ ordering 42, and then to use the offer with the pair p₂ and p₃ (they pay 30) and with the pair p₄ and p₅ (they pay 42), for a total price of 72.

Given n and the prices of the dishes, can you find out what is the minimum total amount that Ivan and his friends have to pay?

Input

Input consists of several cases, only with integer numbers. Each case begins with n, followed by the total number of dishes k, followed by the prices of the dishes, all between 1 and 100. Assume 1 ≤ n ≤ k ≤ 1000.

Output

Print the minimum total price that Ivan and his friends can achieve thanks to the 2 × 1 offer.