Có \(n\) ngôi nhà nằm trên một con đường, được đánh số \(1, 2, \ldots, n\). Khoảng cách từ ngôi nhà \(a\) đến \(b\) là \(|a - b|\). Bạn biết được số đứa trẻ trong từng căn nhà.

Nhiệm vụ của bạn là thành lập \(k\) ngôi trường sao cho mỗi ngôi trường nằm ở một căn nhà nào đó. Sau đó, những đứa trẻ sẽ đi học ở trường gần chúng nhất. Tổng quãng đường đi bộ nhỏ nhất của những đứa trẻ là gì nếu bạn thực hiện một cách tối ưu?

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): số ngôi nhà và số ngôi trường. Các ngôi nhà được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) : số đứa trẻ trong mỗi nhà.

Output

In ra tổng quãng đường nhỏ nhất.

Constraints

• \(1 \leq k \leq n \leq 3000\)
• \(1 \leq c_i \leq 10^9\)

Example

Sample Input

6 2
2 7 1 4 6 4

Sample Output

11