카드 합체 놀이

자연수가 적힌 카드 $n$장이 있다. 처음에 $i$번 카드에는 $a_i$가 적혀 있다. 카드 합체는 다음 과정을 따른다.

1. 서로 다른 두 카드 $x$번 카드와 $y$번 카드를 고르고 두 수의 합을 계산한다. ($x \ne y$)
2. 계산한 값을 $x$번 카드와 $y$번 카드에 모두 덮어쓴다.

카드 합체를 총 $m$번 수행한 뒤 $n$장 카드에 적힌 수의 합이 점수가 된다. 점수가 가장 작아지도록 합체할 카드를 고를 때 만들 수 있는 가장 작은 점수를 구한다.

첫 번째 줄에 카드의 개수 $n$($2 \le n \le 1000$)과 합체 횟수 $m$($0 \le m \le 15n$)이 공백으로 구분되어 주어진다.

두 번째 줄에 처음 카드에 적힌 $n$개의 자연수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 1000000$)

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.