Задача F. Магазин

Автор:Жюри ВКОШП-2011 | Автор задачи: Николай Ведерников, Автор условия: Николай Ведерников   Ограничение времени:2 сек
Входной файл:shop.in   Ограничение памяти:256 Мб
Выходной файл:shop.out  

Условие

У Билла большая семья: трое сыновей, девять внуков. И всех надо кормить. Поэтому Билл раз в неделю ходит в магазин.

Однажды Билл пришел в магазин и увидел, что в магазине проводится акция под названием "каждый k-й товар бесплатно". Изучив правила акции, Билл выяснил следующее. Пробив на кассе товары, покупатель получает чек. Пусть в чеке n товаров, тогда n/k округленное вниз самых дешевых из них достаются бесплатно.

Например, если в чеке пять товаров за 200, 100, 1000, 400 и 100 рублей, соответственно, и k = 2, то бесплатно достаются оба товара по 100 рублей, всего покупатель должен заплатить 1600 рублей.

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

Помогите Биллу выяснить, какую минимальную сумму он сможет заплатить за выбранные товары, возможно разбив их на несколько чеков.

В приведенном примере Билл может разбить товары на два чека: в один чек пойдут товары за 1000 и за 400 рублей, товар за 400 рублей в этом чеке достанется бесплатно, а в другой — остальные товары, в нем бесплатно достанется один товар за 100 рублей. Итого Биллу придется заплатить 1300 рублей.

Формат входного файла

Первая строка входного файла содержит два целых числа n, k (1 ≤ n ≤ 100 000, 2 ≤ k ≤ 100) — количество товаров, которые хочет купит Билл и параметр акции "каждый k-й товар бесплатно".

Следующая строка содержит n целых чисел ai (1 ≤ ai ≤ 10 000) — цены товаров, которые покупает Билл.

Формат выходного файла

Выведите в выходной файл одно число — минимальную сумму, которую должен заплатить Билл за товары.

Примеры тестов

Входной файл (shop.in) Выходной файл (shop.out)
1
5 2
200 100 1000 400 100
1300

0.034s 0.007s 15