Nhà kính của Sprout

Giáo sư Pomona Sprout đang chăm sóc khu vườn Thảo Dược Học tại Hogwarts. Dọc theo một lối đi dài trong khu vườn, có $N$ cây thảo dược quý hiếm được trồng tại các vị trí khác nhau trên một đường thẳng. Cây thứ $i$ nằm ở vị trí $x_i$.

Để bảo vệ các cây khỏi thời tiết khắc nghiệt, giáo sư Sprout cần đặt đúng $K$ nhà kính dọc theo lối đi. Mỗi nhà kính có thể được đặt tại bất kỳ vị trí số nguyên nào trên đường thẳng.

Mỗi cây sẽ được bảo vệ bởi nhà kính gần nó nhất. Tuy nhiên, hiệu quả bảo vệ giảm dần theo khoảng cách: chi phí bảo trì cho cây thứ $i$ bằng khoảng cách từ cây đó đến nhà kính gần nhất, tức là $|x_i-g|$ với $g$ là vị trí nhà kính gần nhất.

Giáo sư Sprout muốn đặt $K$ nhà kính sao cho tổng chi phí bảo trì của tất cả các cây là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$ - số cây thảo dược và số nhà kính.
• Dòng thứ hai chứa $N$ số nguyên $x_1,x_2,\dots ,x_N$ - vị trí của các cây trên đường thẳng.

Dữ liệu ra

• In ra một số nguyên duy nhất - tổng chi phí bảo trì nhỏ nhất có thể.

Ràng buộc

• $1\le K\le N\le 100000$
• $1\le K\le 300$
• $1\le x_i\le {10}^9$
• Các vị trí $x_i$ không nhất thiết phải phân biệt.

Ví dụ