Nhà và Trường

Có $n$ ngôi nhà xếp thành một hàng, nhà thứ $i$ có $c_i$ trẻ em. Hãy chọn đúng $k$ ngôi nhà để xây trường học sao cho tổng quãng đường đi học của tất cả trẻ em là nhỏ nhất (mỗi em đến trường gần nhất).

Khoảng cách giữa nhà $i$ và nhà $j$ là $|i-j|$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $k$.
• Dòng 2: $n$ số nguyên $c_1,c_2,\dots ,c_n$.

Dữ liệu ra

• Một số nguyên: tổng quãng đường nhỏ nhất.

Ràng buộc

• $1\le k\le n\le 3000$
• $1\le c_i\le {10}^9$

Ví dụ