spoj
Състезание
Задача
H
Наименование
SUPERMARKET

Условие

H. СУПЕРМАРКЕТ
---
Чичо Скрудж има голямо семейство: трима сина и девет внука. И всички те искат да ядат. Ето защо, чичо Скрудж веднъж седмично ходи в супермаркета. Веднъж, като отишъл в магазина, попаднал на промоция с мото "Всяка най-евтина K-та стока – безплатна!". След като разучил правилата на промоцията чичо Скрудж разбрал следното: когато отиде на касата с избраните стоки, купувачът получава ваучер. Нека ваучерът съдържа N стоки. Тогава най-евтините | N/K |  от тях са безплатни ( | x | е долната цяла част на x). Например, ако във ваучера има 5 стоки за 200, 100, 1000, 400 и 100 пари и K = 2, то | 5/2 | = 2, тогава безплатни ще бъдат двете стоки по 100 пари и клиентът ще трябва да заплати общо 1600 пари.

Знаете, че чичо Скрудж е скъперник и преди да отиде на касата съобразил, че може да раздели избраните стоки на групи и за всяка да получи отделен ваучер така, че да изхарчи по-малко пари. С него, както обикновено, е и Жълтото пате, което помага на чичо си в покупките. Чичо Скрудж му възложил да раздели стоките в групи за да се възползват от промоцията по оптимален начин. Помогнете им, като напишете програма, която определя минималната сума, която може да се заплати за избраните стоки,  ако се разделят в няколко групи.

Вход: 
Програмата трябва да може да обработва няколко примера при едно изпълнение. На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери. За всеки тестов пример, на първия ред са зададени две цели числа – броят N на стоките, които чичо Скрудж иска да купи и параметъра K на акцията "Всяка най-евтина K-та стока – безплатна!". Следващият ред съдържа N цели числа, като i-тото от тях е цената Ai на i-тата стока, която ще купи чичо Скрудж.
 
Изход: 
За всеки пример програмата трябва да изведе на отделен ред на стандартния изход минималната сума, която чичо Скрудж трябва да плати за стоките. 

Ограничения: 
1 ≤ N ≤ 100000, 2 < K ≤ 100, 1 ≤ Ai ≤ 10000.

Примерен вход:
1
5 2
200 100 1000 400 100	

Примерен изход:
1300

Пояснение: 
В посочения пример чичо Скрудж може да раздели покупките на две групи: в едната ще отидат стоки за 1000 и за 400 пари и тогава стоката за 400 пари ще бъде безплатна, а в другата група ще бъдат останалите стоки и тогава една от стоките за 100 пари ще бъде безплатна и чичо Скрудж ще плати само 1300 пари.

« Предходна страница Решение Въпрос