#3168. 山区建小学

山区建小学

题目描述

政府在某山区修建了一条道路,恰好穿越总共mm个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为did_i(为正整数),其中,0<i<m0 < i < m。为了提高山区的文化素质,政府又决定从mm个村中选择nn个村建小学(设0<nm<5000 < n ≤ m < 500)。请根据给定的mmnn以及所有相邻村庄的距离,选择在哪些村庄建小学,才使得所有村到最近小学的距离总和最小,计算最小值。

输入

第1行为mmnn,其间用空格间隔

第2行为m1m-1 个整数,依次表示从一端到另一端的相邻村庄的距离,整数之间以空格间隔。

例如:

10 3
2 4 6 5 2 4 3 1 3

表示在1010个村庄建33所学校。第11个村庄与第22个村庄距离为22,第22个村庄与第33个村庄距离为44,第33个村庄与第44个村庄距离为66,...,第99个村庄到第1010个村庄的距离为33

输出

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

样例

10 2
3 1 3 1 1 1 1 1 3
18

来源

一本通在线评测