В последнее время крупные магазины все чаще стали предлагать своим покупателям различные дисконтные программы. И если в некоторых магазинах условия получения скидки запутанны и сложны, то в гипермаркете «Скип» все предельно ясно: каждый K-й товар в чеке достается покупателю бесплатно.

Студент всегда не прочь сэкономить. Но голова студента забита совсем другими вещами, поэтому он вспоминает о действующей системе скидок только тогда, когда все его N товаров уже выложены на конвейерную ленту перед кассой.

Кассир берёт товары с ленты по очереди. В этот момент студент может попросить кассира пока не пробивать взятый им товар, и переложить его в конец ленты. Кассир и вся очередь терпеливо ждут, пока студент переложит товар в конец ленты, после чего ситуация повторяется снова. Если студент решает не перекладывать товар, то он пробивается в чек и исчезает с ленты. Если какой-то товар студент уже перекладывал, то, чтобы не нервировать очередь за собой, он в любом случае разрешает кассиру пробить его в чек. Известно, что все товары, приобретаемые студентом, различны, хотя и могут иметь одинаковую стоимость.

Рассмотрим пример. Пусть стоимости товаров на ленте в порядке от ближайшего к кассиру до самого дальнего составляют 4, 1, 3 и 2 рубля, соответственно. Тогда при K = 2 студенту придется заплатить всего 7 рублей. Однако если бы товары лежали на конвейерной ленте в порядке 1, 3, 2, 4, то студент заплатил бы всего 3 рубля. Чтобы из первой ситуации получить вторую, студент может переложить товар стоимостью 4 рубля в конец ленты, сэкономив таким образом 4 рубля.

Зная цены товаров, их первоначальный порядок на ленте, а так же число K, помогите студенту определить минимальное количество денег, необходимое для приобретения всех товаров.