В местном магазине недалеко от вас вовсю готовятся к великому празднику Черной пятницы. Всего на витрине есть \(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\).
Так что вы, будучи наивным покупателем, не заботитесь о том, сколько денег вы потратите. Вы же, однако, хотите, чтобы суммарная цена предметов, которые вы получите бесплатно, была как можно больше.
Какая наибольшая суммарная цена может быть у предметов, которые вы получите бесплатно за одну покупку?