Економія центів#7853
Для проведення регіонального конкурсу, такого як NWERC, необхідна підготовка: організація кімнат і комп'ютерів, створення хорошого набору задач, запрошення учасників, проєктування футболок, бронювання номерів у готелях тощо. Я відповідаю за закупівлі в супермаркеті.
Коли я доходжу до каси, я кладу всі свої товарів на стрічку конвеєра і чекаю, поки всі інші клієнти переді мною в черзі не будуть обслужені. Очікуючи, я розумію, що цей супермаркет нещодавно почав округляти загальну ціну покупки до найближчого кратного центів (при центах округлення відбувається вгору). Наприклад, центи округлюються до , а центів — до .
Можна розділити мій кошик покупок на групи й оплачувати їх окремо. Мені вдалося знайти роздільники, щоб розділити товари на d + 1 групу. Мені цікаво, де поставити роздільники, щоб мінімізувати загальну вартість усіх товарів. Оскільки у мене мало часу, я не хочу переставляти товари на стрічці конвеєра.
Складається з:
рядка з двох чисел (1 \leq n \leq 2000) і (1 \leq d \leq 20) — кількість товарів і кількість доступних роздільників;
рядка з цілих чисел p_1, \ldots, p_n (1 \leq p_i \leq 10000 для 1 \leq i \leq n) — ціна кожного товару в центах. Ціни подані у тому ж порядку, що й товари на стрічці конвеєра.
Виведіть мінімальну суму грошей, необхідну для купівлі всіх товарів, використавши не більше роздільників.
Приклад 1
Приклад 2