Экономия

Представь, что ты - капитан команды, которая только что выиграла мировой финал ACM ICPC, и теперь тебе предстоит отпраздновать свою победу со своими друзьями, которых у тебя ровно K-1. Для этого необходимо закупить N бутылок любимого напитка (остается только догадываться какого) в ближайшем магазине. Стоимость i-й бутылки составляет C_i рублей. К сожалению, продавец не любит, когда его клиенты покупают слишком много бутылок, поэтому он продаёт только по одной бутылке за раз, а также изменяет цену бутылки для клиента, который ранее у него уже делал покупки. Точнее, если клиент уже купил X бутылок, то он должен заплатить (X+1)*C_i рублей, чтобы купить бутылку номер i.

Необходимо определить минимально возможную стоимость приобретения N бутылок с учетом того, что в процессе покупки могут участвовать не более K человек (только ты и твои друзья).

Входные данные

Первая строка входного файла INPUT.TXT содержит два числа N и K (N, K ≤ 100), соответственно во второй строке определены значения C₁, C₂, ..., C_N ( C_i ≤ 10⁶). Все числа во входных данных натуральные.

Выходные данные

В выходной файл OUTPUT.TXT выведите оптимальную стоимость покупки.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]