Card merge game

You have $n$ cards with natural numbers. Card $i$ shows $a_i$ at the start. One merge follows these steps.

1. Choose two different cards, card $x$ and card $y$, and compute the sum of the two numbers. ($x \ne y$)
2. Write the computed value on both card $x$ and card $y$.

After $m$ merges, the score is the sum of the numbers on all $n$ cards. Choose the cards to merge so the score is as small as possible, and compute the smallest possible score.

The first line contains the number of cards $n$ ($2 \le n \le 1000$) and the number of merges $m$ ($0 \le m \le 15n$), separated by a space.

The second line contains the $n$ initial natural numbers $a_1, a_2, \dots, a_n$, separated by spaces. ($1 \le a_i \le 1000000$)

Print the smallest possible score on the first line.