小鑫の日常系列故事(三)——上学路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  小鑫的家到学校有一条很长很长的路,每当上学时小鑫都要通过这条路上学。
  为了方便人们的出行,这条路上建有n个传送阵,我们给它依次编号为C1……Cn。传送阵C1在小鑫家门口,传送阵Cn在学校(别问我为什么,我只知道他家很有钱)。每两个传送之间都有一段路,总共有n-1段路,第i个到第i+1个传送阵之间的路编号为i。小鑫在去上学的时候需要Ti长的时间来走过第i段路。
  这条路虽然很长,但是小鑫的妈妈不想让他每天都借助传送阵直接去上学。于是当每天上学时,妈妈总会给小鑫一些钱。这些钱只能让小鑫使用m次传送阵,这样就可以让小鑫走几段路来锻炼身体了。
  小鑫总想在路上消耗的时间最小,你能帮他解决问题吗?
  Ps:已知当他使用一次传送阵的时候,他可以瞬间由第i个传送阵传送到第i+1个,也就是说当他使用第i个传送阵时,将会有Ti的时间被节省。

Input

第一行为两个数n,m。5<n<100, 0<=m<=n-1
第二行为n-1个数T1……Tn-1.  0<Ti<300

Output

只有一行,为最小花费时间。

Sample Input

4 1
1 2 3

Sample Output

3

Hint

 

Source

lin