題目描述

在遙遠的某處，有個王國叫法爾薩斯。

 

有一天，邪惡(?)的魔女要進攻法爾薩斯，她準備了n個破壞性極強的魔法，第i個魔法的威力為a[i]，並且順序地釋放。

 

而幸運的是，法爾薩斯的國王有著一把可以斬斷所有魔法的王劍----阿卡西亞。他準備用這把王劍去對抗魔女。

 

國王可以斬斷任意k個魔法，但是在斬斷第i個魔法時，那麽這個魔法的威力會變為0，但會令隨後的所有魔法威力增加1。

 

舉個例子：

如果國王選擇斬斷第2,3個魔法，則第2和第3個魔法的威力會變為0，但第4個魔法的威力會變為a[4]+2。

 

因為法爾薩斯的城堡己經被弄壞了一遍，國王不想剛剛修好又被破壞了。所以希望你可以幫他計算，法爾薩斯承受魔法威力總和的最小值為多少?

輸入格式

在輸入數據的第一行中，有一個正整數T（1<=T<=10），表示測試數據的組數。每組測試數據的輸入描述如下。

每組測試數據的第一行包含兩個正整數n和k（0<=n,k<=10000，k<=n），分別為魔法的數量及可以斬斷魔法的次數。

隨後有一行n個數字a[1],a[2],a[3]…a[n] (a[i]<=10^9)，a[i]為第i個魔法的威力。

輸出格式

對於每一組數據，需要輸出一行，含有一個整數，表示法爾薩斯承受魔法威力總和的最小值。

Samples

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

0
21
9
6
0

提示

對於第1組測試數據，n=k。

對於第2-3組測試數據，k=0。

對於第4-10組測試數據，無限制。

原始資料

• Zero1 題號：a742
• Hydro 題號：Z0742
• Locale：zh_TW
• Display：practice