题目描述

一条道路依次经过 $m$ 个村庄，相邻村庄距离已知。要从这些村庄中选出 $n$ 个建设小学，使所有村庄到最近小学的距离之和尽可能小，求这个最小值。

输入格式

第1行为m和n，其间用空格间隔 第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。

例如 10 3 2 4 6 5 2 4 3 1 3 表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。

输出格式

各村庄到最近学校的距离之和的最小值。

样例

10 2
3 1 3 1 1 1 1 1 3

18

数据范围

$1\le n\le m<500$，每段相邻距离为 $1$ 至 $10^6$ 的整数。