题目背景

翻译自 CSES-2087 题。

题目描述

在一条街道上，有 $n$ 所房屋，编号为 $1, 2, ..., n$。房屋 $a$ 和房屋 $b$ 之间的距离是 $|a - b|$。你知道每所房屋里有多少个孩子。

你的任务是建立 $k$ 所学校，使得每所学校都位于某一所房屋中。然后，每个孩子都将前往最近的学校。请问，若你采取最优策略，孩子们的总步行距离最小是多少？

输入格式

第一行输入两个整数 $n$ 和 $k$，分别表示房屋的数量和学校的数量。房屋的编号为 $1, 2, ..., n$。

接下来，输入 $n$ 个整数 $c_1, c_2, ..., c_n$，表示每所房屋中的孩子数量。

输出格式

输出一个整数，表示孩子们的最小总步行距离。

样例

6 2
2 7 1 4 6 4

11

样例1解释

最优解是将学校设置在第 $2$ 所房屋和第 $5$ 所房屋。此时，孩子们的总步行距离为 $11$。

说明/提示

$1 \leq k \leq n \leq 3000$；

$1 \leq c_i \leq 10^9$。