24362번 - МАГАЗИН 다국어

Дядо Тодор има голямо семейство: трима сина и девет внука. И всички те трябва да се хранят. Затова веднъж седмично, той ходи в магазина.

Като влязъл в магазина днес видял, че се провежда акция под името «всяка k–та стока безплатна». Правилата на акцията са следните: Купувачът показва стоките на касата в магазина и получава чек. Ако чекът е за n стоки, то n/k (закръглено надолу) на брой от най-евтините стоки са безплатни.

Например: ако чекът е за 5 стоки по 20, 10, 100, 40 и 10 лева, съответно, и k = 2, то безплатни ще бъдат двете стоки по 10 лв. Тогава клиентът ще трябва да плати общо 160 лв.

Дядо Тодор избрал стоките и се отправил към касата. Тогава съобразил, че стоките, които иска да купи, може да раздели на няколко чека, и тогава ще похарчи по-малко пари.

Напишете програма shop, която намира минималната сума, която трябва да плати дядо Тодор за избраните стоки, като е възможно да ги раздели на няколко чека.

От първия ред на стандартния вход се въвеждат две цели числа n и k – брой на стоките, които дядо Тодор иска да купи, и параметъра на акцията «всяка k–та стока безплатна». Числата са разделени с един интервал.

От следващия ред се въвеждат n цели числа ai – цените на стоките, които купува дядо Тодор. Числата са разделени с по един интервал.

На един ред на стандартния изход програмата трябва да изведе едно цяло число – минималната сума, която трябва да плати дядо Тодор за стоките.

• 1 ≤ n ≤ 100 000
• 2 ≤ k ≤ 100
• 1 ≤ a_i ≤ 10 000

Дядо Тодор може да раздели стоките на два чека:

• В единия чек да бъдат стоките за 100 и за 40 лв. Стоката за 40 лв ще бъде безплатна;
• В другия чек – останалите стоки. В него безплатна ще е една стока за 10 лв.

Тогава трябва да се плати общо 130 лв.