柏林军队正在准备一场大规模的阅兵式。参加的士兵将被分成人数相等的 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 的士兵人数。
输出每组数据中可以参加游行的士兵的最大数量。（每两个答案中间有一个换行）
5 3 4 7 1 13 1 1 100 1 3 100 2 1 1000000000000 1000000000000 4 1 10 2 11 1
16 100 99 2000000000000 13
样例说明
第一组数据，士兵可以站成这样： [3,3,3,3],[1,2,1,1],[1,1,1,1],[3,3,3,3] （每个方括号表示一行）；
第二组数据，所有士兵可以全部站成一排；
第三组数据，士兵可以站成 3 排，每排 33 人；
第四组数据，所有士兵可以全部站成一排；
第五组数据，所有身高为 2 和 3 的可以站成一排。