← 返回题目列表

Codeforces · 1431/C

C. 黑色星期五

中文机器翻译题面 查看原题

您所在地区有一家当地商店正在为黑色星期五的伟大假期做好准备。显示屏上有 $$$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