Card merge game

Interview

Time limit1sMemory limit512 MB

Summary

Each merge replaces two chosen cards with their sum; after exactly m merges, minimize the total sum of all cards.

Level: Medium5 of 10
Topics: Greedy, Heap, Simulation, Implementation
Solved: No attempts yet

Problem

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

Choose two different cards, card $x$ and card $y$ , and compute the sum of the two numbers. ( $x \ne y$ )
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.

Input

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$ )

Output

Print the smallest possible score on the first line.

Examples2

Example 1
Input
```
3 1
3 2 6
```
Expected output
```
16
```
Example 2
Input
```
4 2
4 2 3 1
```
Expected output
```
19
```