Năm Ất Tỵ đến, hàng đàn rắn từ khắp nơi đổ về MixiLand ăn mừng — ai bảo đây là năm của chúng cơ chứ? Anh DoMixi, với tinh thần trách nhiệm của một streamer hàng đầu, quyết định ra tay "tiếp đón" lũ rắn theo cách riêng của mình: bắt sạch ~N~ đàn rắn đang xếp hàng dọc theo con đường làng rồi nhốt chúng lại cho gọn.

Anh DoMixi có một cái lưới. Lưới có kích thước ~s~ nghĩa là anh chỉ bắt được đàn rắn có tối đa ~s~ con. Mỗi khi bắt xong một đàn, anh nhốt chúng vào lồng và tiếp tục với đàn tiếp theo bằng lưới trống. Các đàn rắn phải được bắt theo thứ tự từ trái sang phải.

Khi bắt đàn rắn có ~g~ con bằng lưới kích thước ~s~, anh sẽ lãng phí ~s - g~ ô lưới. Anh DoMixi muốn tổng số ô lãng phí càng nhỏ càng tốt — chat toàn nhắc anh phải tiết kiệm mà.

Lưới có thể bắt đầu ở bất kỳ kích thước nào, và anh được phép thay đổi kích thước lưới đúng ~K~ lần trong suốt quá trình bắt rắn (thay đổi có thể tăng hoặc giảm tùy ý).

Hãy giúp anh DoMixi tính tổng số ô lưới lãng phí ít nhất có thể!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~.

Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~, trong đó ~a_i~ là số rắn trong đàn thứ ~i~.

Kết quả

In ra một số nguyên duy nhất — tổng số ô lưới lãng phí nhỏ nhất.

Ví dụ

Đầu vào:

6 2
7 9 8 2 3 2

Đầu ra:

3

Giải thích: Anh DoMixi bắt đầu với lưới kích thước ~7~. Sau đàn 1, anh đổi lên ~9~ và giữ nguyên đến đàn 3. Sau đàn 3, anh đổi xuống ~3~. Tổng lãng phí: ~(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2) = 3~.

Giới hạn

• ~1 \le N \le 400~
• ~1 \le K < N~
• ~0 \le a_i \le 10^6~

Subtask