题目描述

小青出身新东方，所以对于烹饪他可是很在行的。

可是他的数学不怎么好。

今晚他想在家做顿丰盛的晚餐招待他的女盆友，为什么呢？因为他想向女友

炫耀下他的烹饪技能。

所以捏，小青决定准备n道菜，第i个菜含有Ai个的步骤。

菜应该按步骤顺序完成，在烹饪的每一分钟，小青

最多可以选择M道不同的菜肴and完成选择菜的一个步骤。</strong>

教练高想知道他需要准备晚餐最少的时间。你来帮他计算咯~o(∩_∩)o

输入格式

有多组测试数据，先输入T,表示有T组测试数据。

</p>

然后给出两个整数 

N and M (1 <= N, M <= 40000). </span>

接下来是</span>

N 个整数 A</span>_</p>

i

 (1 <= A</span>_</p>

i

 <= 40000).</span>

</p>

输出格式

对于每组数据都只输出一行，即完成所有菜的最少时间。

样例

样例 1

输入 # 1

样例

样例 1

输入 # 1

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

输出 # 1

3
10