센트 절약

지역 프로그래밍 대회를 열려면 준비할 일이 많다. 시험장과 컴퓨터를 마련하고, 좋은 문제 세트를 만들고, 참가자를 초청하고, 티셔츠를 디자인하고, 호텔 방을 예약한다. 나는 슈퍼마켓 장보기를 맡았다.

계산대에 도착해서 물건 n개를 모두 컨베이어 벨트에 올려놓고, 앞에 선 다른 손님의 계산이 끝나기를 기다린다. 기다리다가 이 슈퍼마켓이 얼마 전부터 결제 총액을 가장 가까운 10센트 단위로 반올림한다는 사실을 떠올린다. 5센트는 올림한다. 예를 들어 94센트는 90센트가 되고, 95센트는 100센트가 된다.

물건을 여러 묶음으로 나눠서 따로 결제할 수 있다. 구분자 d개를 구했으므로 최대 d + 1개의 묶음으로 나눌 수 있다. 결제 총액이 가장 적어지도록 구분자를 어디에 놓을지 정하려고 한다. 시간이 없어서 벨트 위 물건의 순서는 바꾸지 않으므로, 각 묶음은 벨트에서 연속한 물건으로 이루어진다.

입력은 다음과 같이 주어진다.

• 첫째 줄에 정수 n과 d가 주어진다 ($1 \le n \le 2000$, $1 \le d \le 20$). n은 물건의 개수, d는 쓸 수 있는 구분자의 개수다.
• 둘째 줄에 정수 $p_1, \ldots, p_n$이 주어진다 ($1 \le p_i \le 10000$). $p_i$는 i번째 물건의 가격이며 센트 단위다. 가격은 물건이 벨트에 놓인 순서대로 주어진다.

구분자를 최대 d개 써서 물건을 모두 살 때 드는 최소 금액을 출력한다.