题目描述
山间一条公路依次串起 $m$ 个村子（无岔路）。乡里要沿路开设 $n$ 个快递驿站（$0 < n \le m$）， 每个村子归距离最近的驿站服务。第 $i$ 与第 $i+1$ 个村子相距 $d_i$ 米。
请规划驿站位置，使所有村子到各自最近驿站的距离总和最小，输出这个最小值。
输入格式
第一行两个整数 $m, n$，用空格分开； 第二行 $m-1$ 个整数，为相邻村子的距离 $d_1, \ldots, d_{m-1}$。
输出格式
一行，一个整数：所有村子到最近驿站距离总和的最小值。
数据范围
$$0 < n \le m < 500$$
，距离为正整数。