Problem D
Cent Savings
When I get to the cash register, I put all my $n$ items on the conveyor belt and wait until all the other customers in the queue in front of me are served. While waiting, I realize that this supermarket recently started to round the total price of a purchase to the nearest multiple of $10$ cents (with $5$ cents being rounded upwards). For example, $94$ cents are rounded to $90$ cents, while $95$ are rounded to $100$.
It is possible to divide my purchase into groups and to pay for the parts separately. I managed to find $d$ dividers to divide my purchase in up to $d+1$ groups. I wonder where to place the dividers to minimize the total cost of my purchase. As I am running out of time, I do not want to rearrange items on the belt.
Input
The input consists of:
-
one line with two integers $n$ ($1 \leq n \le 2\, 000$) and $d$ ($1 \leq d \le 20$), the number of items and the number of available dividers;
-
one line with $n$ integers $p_1, \ldots p_ n$ ($1 \leq p_ i \leq 10\, 000$ for $1 \le i \le n$), the prices of the items in cents. The prices are given in the same order as the items appear on the belt.
Output
Output the minimum amount of money needed to buy all the items, using up to $d$ dividers.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 13 21 55 60 42 |
190 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 1 1 1 1 1 |
0 |
