МАГАЗИН
면접 대비시간 제한1초메모리 제한1024 MB
n개의 상품을 여러 영수증으로 나눌 수 있을 때, 각 영수증마다 가장 싼 floor(개수/k)개가 무료가 되도록 하여 지불 총액을 최소로 만든다.
문제
Дядо Тодор има голямо семейство: трима сина и девет внука. И всички те трябва да се хранят. Затова веднъж седмично, той ходи в магазина.
Като влязъл в магазина днес видял, че се провежда акция под името «всяка 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 ≤ ai ≤ 10 000
힌트
Дядо Тодор може да раздели стоките на два чека:
- В единия чек да бъдат стоките за 100 и за 40 лв. Стоката за 40 лв ще бъде безплатна;
- В другия чек – останалите стоки. В него безплатна ще е една стока за 10 лв.
Тогава трябва да се плати общо 130 лв.