Theo truyền thuyết, St. Patrick đã đuổi toàn bộ rắn khỏi Mooland hơn một nghìn năm trước. Nhưng rắn đã quay lại! Ngày Thánh Patrick là ngày 17 tháng 3, nên Bessie sẽ tưởng nhớ St. Patrick bằng cách đuổi mọi con rắn khỏi Mooland mãi mãi.

Bessie có một chiếc lưới để bắt rắn phân bố thành $N$ nhóm trên một đường thẳng $(1 \leq N \leq 400)$. Cô phải bắt mọi con rắn trong từng nhóm theo thứ tự các nhóm trên đường. Sau mỗi nhóm, cô có thể bỏ rắn vào lồng và bắt nhóm tiếp theo bằng lưới rỗng.

Lưới cỡ $s$ có thể bắt một nhóm $g$ con rắn nếu $g \leq s$. Nhưng mỗi lần bắt nhóm cỡ $g$ bằng lưới cỡ $s$, cô lãng phí $s - g$ chỗ. Lưới ban đầu có thể có bất kỳ cỡ nào và cô có thể đổi cỡ $K$ lần $(1 \leq K < N)$.

Hãy cho Bessie biết tổng chỗ lãng phí nhỏ nhất sau khi bắt tất cả các nhóm.

Dữ liệu vào

Dòng đầu chứa $N$ và $K$. Dòng thứ hai chứa $N$ số nguyên $a_1,\dots,a_N$, trong đó $a_i$ ($0 \leq a_i \leq 10^6$) là số rắn ở nhóm thứ $i$.

Dữ liệu ra

In một số nguyên là lượng chỗ lãng phí nhỏ nhất sau khi bắt tất cả rắn.

Ví dụ

Dữ liệu vào 1

6 2
7 9 8 2 3 2

Dữ liệu ra 1

3

Ghi chú

Lưới ban đầu có cỡ 7. Sau nhóm đầu, Bessie đổi thành 9 và giữ cỡ đó đến nhóm thứ 4, khi cô đổi thành 3. Tổng chỗ lãng phí là $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

Tác giả bài toán: Patrick Zhang