Citlali đang muốn tổ chức một bữa tiệc ở nhà mình, bà đã chuẩn bị rất nhiều đồ ngọt cho các vị khách của mình. Nhưng khổ nỗi, bà lại quên không chia phần các miếng bánh của mình.

Vì quá lười và chỉ muốn nằm ngủ, nên bà đã ép Aether giúp mình chia chúng. Aether cũng đang rất bối rối không biết phải làm như nào, nên anh đã gọi cho bạn để cầu cứu.

Citlali có ~N~ miếng bánh, kích thước của từng miếng bánh là ~a_i~ và kích thước của chúng là lớn dần. Bạn được nhờ chia số bánh này ra thành ~K~ phần liên tiếp, với chi phí chia cho một phần ~a_l~ đến ~a_r~ là ~max(a_{l..r}) - min(a_{l..r})~.

Citlali muốn số tiền bà mất là ít nhất (bà làm gì có tiền), nên bạn cần tính giá trị này

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~K~: số miếng bánh và số phần bánh phải chia

Dòng thứ 2 chứa ~N~ số nguyên: kích thước của ~N~ miếng bảnh

Output

In ra kết quả của bài toán: chi phí chia bánh ít nhất.

Giới hạn

~1 <= K <= N <= 3*10^5~ ~1 <= a_i <= 10^9~

Test mẫu

Input

6 3
4 8 15 16 23 42

Output

12