Економія центів
Для проведення регіонального змагання, такого як NWERC, необхідно приготування: організація кімнат і комп'ютери, створення хорошого набору завдань, запрошення конкурсантів, проектування футболок, бронювання номерів у готелях і так далі. Я відповідаю за відвідування магазину в супермаркеті.
Коли я добираюся до каси, я кладу всі свої n предметів на конвеєр і чекаю, поки всі інші клієнти в черзі переді мною будуть обслужені. Чекаючи, я розумію, що цей супермаркет недавно почав округляти загальну ціну покупки до найближчого кратного в 10 центів (при 5 центах округлення відбувається вгору). Наприклад 94 центів округлятиметься до 90, в той час як 95 центів округлятиметься до 100.
Можна розділити мої покупки на групи і окремо їх оплачувати. Мені вдалося знайти d роздільників, щоб розділити покупки на d + 1 групу. Мені цікаво, де розмістити роздільники, щоб мінімізувати загальну вартість всіх покупок. Оскільки у мене закінчується час, я не хочу переставляти предмети на стрічці.
Вхідні дані
Вона складається з:
рядок містить два числа n (1 ≤ n ≤ 2000) і d (1 ≤ d ≤ 20) - кількість покупок і кількість наявних роздільників;
рядок з n цілих чисел
p[1], ...,p[n](1 ≤p [i]≤ 10000 для 1 ≤ i ≤ n) - ціни покупок в центах. Ціни задані в тому ж порядку в якому покупки розміщені на стрічці.
Вихідні дані
Вивести найменшу кількість грошей, необхідне для покупки всіх продуктів, використовуючи до d роздільників.