C. Черная пятница
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В местном магазине недалеко от вас вовсю готовятся к великому празднику Черной пятницы. Всего на витрине есть $$$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 \rfloor = 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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: наибольшая суммарная цена предметов, которые вы получите бесплатно за одну покупку.

Пример
Входные данные
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
Выходные данные
7
4
6
7
1