2 X 1 P96199


pdf   zip


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

“2 × 1: Bring a companion and one of you (whoever would pay less) eats for free.”

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 p1, p2, p3, p4 and p5 want six dishes with prices 10, 15, 20, 23, 30 and 42, then an optimal solution is to have p1 not ordering anything, p2 ordering 10 and 20, p3 ordering 30, p4 ordering 15 and 23, p5 ordering 42, and then to use the offer with the pair p2 and p3 (they pay 30) and with the pair p4 and p5 (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 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 ≤ nk ≤ 1000.


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

Public test cases
  • Input

    5 6 10 15 20 23 30 42
    2 2 40 30
    2 3 30 30 30


  • Information
    Félix Miravé
    Official solutions
    User solutions