65. GY採香蕉

Problem Description

就事實來說，

1. 搞演算法賺不到錢
2. D_site上面有很多好玩的遊戲
3. 香蕉好吃

基於上述原因，GYLin 最近開始在一個香蕉農場擔任香蕉採收工程師。這份工作的內容主要是將香蕉從樹上摘下來放入袋子中，再將袋子運回倉庫。

農場中有 $N$ 根香蕉，而 GY 總共有 $K$ 個袋子可以用。他發現當兩根香蕉放在同一個袋子時，熟度比較低的香蕉$A$會變得跟熟度比較高的香蕉$B$一樣熟。按照此邏輯，當一堆香蕉放在同一個袋子時，裡面所有香蕉都會變得跟原本袋中最熟的香蕉一樣熟。

想當然耳，為了保存得久，採收完的香蕉當然是越不熟越好。GY 已經算出每根香蕉的熟度：一根香蕉的熟度可以用一個正整數表達，而數字越大表示香蕉越熟。而他想請問你，將每根香蕉都裝入其中一個袋子後，最低的總熟度 (每根香蕉的熟度加總) 可以是多少？

Input Format

在每筆測資中只會有兩行，第一行有兩個整數 $N$ $K$ ，分別代表香蕉數量和袋子數量。接著在第二行會有 $N$ 個數字 $A_1 … A_N$ ，代表每根香蕉的成熟度。

Input Constraints

$1 \leq N \leq 10^4$

$1 \leq A_i \leq 10^5$

$1 \leq K \leq min(10, N)$

Testcase #1~2 : $N \leq 20$ (score: 20)

Testcase #3~4 : $N \leq 10^4$ (score: 80)

Output Format

輸出一個整數：每根香蕉都放入其中一個袋子後，最小的成熟度加總可以為多少。

Sample IO

Sample In 1

6 2
1 2 1 5 2 5

Sample Out 1

18

Sample In 2

6 3
1 2 1 5 2 5

Sample Out 2

16

Sample In 3

10 3
1 1 1 2 3 4 5 6 7 8

Sample Out 3

47

Sample Exbananation

在第一筆測資，我們可以這樣分配得到最小的成熟度加總：

bag 1 = $\{ 1, 1, 2, 2 \}$

bag 2 = $\{ 5,5 \}$

bag 1 的總熟度為 $2+2+2+2=8$ ，bag 2 任何香蕉的熟度都沒有上升。

在第二筆測資，顯然我們能將同樣成熟度的香蕉分配在一起，達到最小成熟度加總。

在第三筆測資，我們可以這樣分配：

bag 1 = $\{ 1,1,1 \}$

bag 2 = $\{ 2,3,4,5 \}$

bag 3 = $\{ 6,7,8 \}$

Judge Setting

run-time limit: 3000 ms
memory limit: 256000000 byte
測資數量: 4