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

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

Можно разделить мои покупки на группы и отдельно их оплачивать. Мне удалось найти d разделителей, чтобы разделить покупки на d + 1 группу. Мне интересно, где разместить разделители, чтобы минимизировать общую стоимость всех покупок. Поскольку у меня заканчивается время, я не хочу переставлять предметы на ленте.

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

Состоит из:

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

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

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

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