问题 26664 --迅速烹饪

26664: 迅速烹饪

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

题目描述

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

可是他的数学不怎么好。
今晚他想在家做顿丰盛的晚餐招待他的女盆友,为什么呢?因为他想向女友
炫耀下他的烹饪技能。

所以捏,小明决定准备n道菜,第i个菜含有Ai个的步骤。
菜应该按步骤顺序完成,在烹饪的每一分钟,小明最多可以选择M道不同的菜肴and完成选择菜的一个步骤。
教练高想知道他需要准备晚餐最少的时间。你来帮他计算咯~o(∩_∩)o

输入

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

然后给出两个整数 N and M (1 <= N, M <= 40000). 接下来是N 个整数 Ai (1 <= Ai <= 40000).

输出

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

样例输入

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

样例输出

3
10

提示

来源

[提交][状态]