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\)
• Dòng thứ hai có \(n\) số nguyên \(c_1, c_2, \ldots, c_n\): số đứa trẻ trong mỗi nhà

Constraints

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

Output

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

Example

6 2
2 7 1 4 6 4

11