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).

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ụ