Для проведення регіонального змагання, такого як NWERC, необхідно приготування: організація кімнат і комп'ютери, створення хорошого набору завдань, запрошення конкурсантів, проектування футболок, бронювання номерів у готелях і так далі. Я відповідаю за відвідування магазину в супермаркеті.

Коли я добираюся до каси, я кладу всі свої n предметів на конвеєр і чекаю, поки всі інші клієнти в черзі переді мною будуть обслужені. Чекаючи, я розумію, що цей супермаркет недавно почав округляти загальну ціну покупки до найближчого кратного в 10 центів (при 5 центах округлення відбувається вгору). Наприклад 94 центів округлятиметься до 90, в той час як 95 центів округлятиметься до 100.

Можна розділити мої покупки на групи і окремо їх оплачувати. Мені вдалося знайти d роздільників, щоб розділити покупки на d + 1 групу. Мені цікаво, де розмістити роздільники, щоб мінімізувати загальну вартість всіх покупок. Оскільки у мене закінчується час, я не хочу переставляти предмети на стрічці.

Вхідні дані

Вона складається з:

• рядок містить два числа n (1 ≤ n ≤ 2000) і d (1 ≤ d ≤ 20) - кількість покупок і кількість наявних роздільників;

• рядок з n цілих чисел p1, ..., pn (1 ≤ p [i] ≤ 10000 для 1 ≤ i ≤ n) - ціни покупок в центах. Ціни задані в тому ж порядку в якому покупки розміщені на стрічці.

Вихідні дані

Вивести найменшу кількість грошей, необхідне для покупки всіх продуктів, використовуючи до d роздільників.