CF1250J The Parade

**题意简述** 柏林军队正在准备一场大规模的阅兵式。参加的士兵将被分成人数相等的$k$行。 当然，排兵布阵是需要一定的规则的：同一排士兵的身高相差不应超过$1$且每个士兵的身高是$1$到$n$之间的整数。 已知每名士兵身高的你必须将所有参加阅兵的士兵排成$k$排，以满足上述条件。请你编写程序计算可以参加游行的士兵的最大数量。

本题**有多组数据**。 第一行包含一个整数$t(1\le t\le 10000)$，表示数据组数。 每组数据都有两行。第一行包含两个整数$n$和$k$（$1≤n≤30000$，$1≤k≤10^{12}$）分别表示不同高度的士兵数量和士兵排数。 第二行包含$n$个整数$c_1,c_2,$ … $,c_n$（$0\le c_i\le 10^{12}$），其中$c_i$表示身高为$i$的士兵人数。

输出每组数据中可以参加游行的士兵的最大数量。（每两个答案中间有一个换行）

第一组数据，士兵可以站成这样：$[3,3,3,3],[1,2,1,1],[1,1,1,1],[3,3,3,3]$（每个方括号表示一行）； 第二组数据，所有士兵可以全部站成一排； 第三组数据，士兵可以站成$3$排，每排$33$人； 第四组数据，所有士兵可以全部站成一排； 第五组数据，所有身高为$2$和$3$的可以站成一排。