Theo truyền thuyết, Thánh Patrick đã xua đuổi tất cả rắn khỏi Mooland hơn một nghìn năm trước. Tuy nhiên, từ đó đến nay rắn đã quay trở lại Mooland! Ngày Thánh Patrick là ngày 17 tháng 3, vì vậy Bessie sẽ tưởng niệm Thánh Patrick bằng cách xua đuổi toàn bộ rắn khỏi Mooland một lần và mãi mãi.

Bessie được trang bị một chiếc lưới để bắt những con rắn phân bố thành \(N\) nhóm trên một đường thẳng (\(1 \leq N \leq 400\)). Bessie phải bắt mọi con rắn trong mọi nhóm theo thứ tự các nhóm xuất hiện trên đường thẳng. Mỗi lần bắt một nhóm, cô có thể cho những con rắn vào lồng và bắt đầu nhóm tiếp theo với chiếc lưới trống.

Một chiếc lưới có kích thước \(s\) nghĩa là Bessie có thể bắt bất kỳ nhóm nào chứa \(g\) con rắn, với \(g \leq s\). Tuy nhiên, mỗi khi Bessie bắt một nhóm gồm \(g\) con rắn bằng chiếc lưới kích thước \(s\), cô lãng phí \(s-g\) đơn vị không gian. Lưới của Bessie có thể bắt đầu với kích thước bất kỳ và cô có thể thay đổi kích thước lưới \(K\) lần (\(1 \leq K < N\)).

Hãy cho Bessie biết tổng lượng không gian lãng phí nhỏ nhất mà cô có thể tích lũy sau khi bắt hết tất cả các nhóm.

Dữ liệu vào

Dòng đầu tiên 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 trong nhóm thứ \(i\).

Dữ liệu ra

In ra một số nguyên là lượng không gian lãng phí nhỏ nhất sau khi Bessie bắt hết tất cả rắn.

Ví dụ

6 2
7 9 8 2 3 2

3

Nguồn

USACO 2019 US Open Contest, Gold — Snakes

Tác giả: Patrick Zhang.