Làm tròn

An đang xếp $N$ món hàng lên băng chuyền để chờ đến lượt tính tiền trong siêu thị. Các món hàng đang được An sắp theo một thứ tự nhất định. Khi chờ đến lượt mình tính tiền thì An được biết siêu thị đang tính tiền làm tròn giá hàng chục đồng. Những đơn hàng có giá tiền ở hàng đơn vị bé hơn $5$ thì làm tròn giá tiền xuống hàng chục gần nhất, đơn hàng có giá tiền ở hàng đơn vị lớn hơn hay bằng $5$ thì làm tròn giá tiền lên hàng chục gần nhất. Ví dụ đơn hàng có giá $94$ đồng thì giá tiền sẽ được làm tròn là $90$ đồng, đơn hàng có giá tiền $95$ đồng thì giá tiền sẽ được làm tròn là $100$ đồng.

An có thể chia $N$ món hàng trên thành nhiều nhóm bằng các thanh chia, mỗi nhóm sẽ được tính tiền riêng (giá của một đơn hàng là tổng giá các món hàng trong nhóm đó, và được làm tròn như trên). An chỉ có thể tìm được $K$ thanh chia để chia thành $(K+1)$ nhóm. Vì thời gian không còn nhiều nên An sẽ không sắp lại thứ tự các món hàng trên băng chuyền mà chỉ đặt các thanh chia ở giữa các món hàng để chia thành nhiều nhóm hàng.

Yêu cầu: Cho biết trước giá tiền của $N$ món hàng và số lượng thanh chia $K$. Hãy viết một chương trình cho biết số tiền nhỏ nhất An phải trả để mua hết $N$ món hàng và không được dùng quá $K$ thanh chia.

Dữ liệu vào

• Dòng đầu là hai số nguyên $N$ và $K$ lần lượt cho biết số món hàng An sẽ mua và số lượng thanh chia.
• Dòng thứ hai chứa $N$ số nguyên dương, mỗi số nhỏ hơn ${10}^5$, là giá tiền của $N$ món hàng, giá tiền được cho theo thứ tự của các món hàng trên băng chuyền.

Dữ liệu ra

In ra một số nguyên là số tiền nhỏ nhất An phải trả để mua hết $N$ món hàng và không được dùng quá $K$ thanh chia.

Ràng buộc

• $1\le N\le 2000$, $1\le K\le 200$.
• Giá mỗi món hàng là số nguyên dương nhỏ hơn ${10}^5$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $1\le N\le 100$, $1\le K\le 20$.
• Subtask 2 ($30\%$ số điểm): $1\le N\le 1000$, $1\le K\le 20$.
• Subtask 3 ($50\%$ số điểm): $1\le N\le 2000$, $1\le K\le 200$.

Ví dụ