您所在地区有一家当地商店正在为黑色星期五的伟大假期做好准备。显示屏上有 $$$n$$$ 商品,价格为 $$$p_1、p_2、\dots、p_n$$$。它们按价格排序,因此 $$$p_1 \le p_2 \le \dots \le p_n$$$。
商店有预先选择的折扣值$$$k$$$。黑色星期五折扣的适用方式如下:单次购买 $$$x$$$ 商品,您可以免费获得其中最便宜的 $$$\lfloor \frac x k \rfloor$$$ 商品($$$\lfloor \frac x k \rfloor$$$ 是 $$$x$$$ 除以 $$$k$$$ 四舍五入到最接近的整数)。您购买的每件商品最多只能包含一次。
例如,如果商店中有价格为 $$$[1, 1, 2, 2, 2, 3, 4, 5, 6]$$$ 的商品,而您购买价格为 $$$[1, 2, 2, 4, 5]$$$ 的商品,并且 $$$k = 2$$$,那么您将获得最便宜的 $$$\lfloor \frac 5 2 \r地板 = 2$$$ 免费。它们是价格为 $$$1$$$ 和 $$$2$$$ 的商品。
所以,作为天真的顾客,你并不关心你花了多少钱。但是,您希望免费获得的物品的总价尽可能大。
单次购买可免费获得的物品总价最高是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。
然后是 $$$t$$$ 测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 200$$$; $$$1 \le k \le n$$$) - 分别是商店中的商品数量和折扣值。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$) — 商店展示的商品价格。这些物品按价格排序,因此 $$$p_1 \le p_2 \le \dots \le p_n$$$。
输出
为每个测试用例打印一个整数:单次购买可以免费获得的物品的最高总价。
示例
输入 #1
5 5 2 1 3 4 6 7 6 3 1 2 3 4 5 6 6 3 3 3 4 4 5 5 1 1 7 4 4 1 3 3 7
输出 #1
7 4 6 7 1