Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Экономия

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

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

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

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

Первая строка входного файла INPUT.TXT содержит два числа N и K (N, K ≤ 100), соответственно во второй строке определены значения C1, C2, ..., CN ( Ci ≤ 106). Все числа во входных данных натуральные.

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

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

Пример

INPUT.TXTOUTPUT.TXT
13 3
2 5 6
13

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru