题目描述

政府在某山区修建了一条道路，恰好穿越总共$\red m$个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。

已知任意两个相邻的村庄之间的距离为$\red{d_i}$（为正整数），其中，$\red{0 < i < m}$。

为了提高山区的文化素质，政府又决定从$m$个村中选择$\red{n}$ 个村建小学（设$\red{0 < n < = m < 500}$）。

请根据给定的$\red{m、n}$以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

输入格式

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

10 3
2 4 6 5 2 4 3 1 3

表示在$\red{10}$个村庄建$\red{3}$所学校。第$\red{1}$个村庄与第$\red{2}$个村庄距离为$\red{2}$，第$\red{2}$个村庄与第$\red 3$个村庄距离为$\red 4$，第$\red 3$个村庄与第$\red 4$个村庄距离为$\red 6$，...，第$\red 9$个村庄到第$\red{10}$个村庄的距离为$\red 3$。

输出格式

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

样例

输入样例

10 2
3 1 3 1 1 1 1 1 3

输出样例

18