#include<bits/stdc++.h> using namespace std; int distant[501][501],cost[501][501],solve[501][501]; int main() { int m,n; cin>>m>>n; for(int i=1;i<m;i++)//输入两村之间的距离 { cin>>distant[i][i+1]; } for(int i=1;i<=m;i++)//计算任意两个村之间的距离 { for(int j=i+1;j<=m;j++) { distant[i][j]=distant[i][j-1]+distant[j-1][j]; distant[j][i]=distant[i][j]; } } for(int i=1;i<=m;i++) { for(int j=i+1;j<=m;j++) { int mid=(i+j)/2; for(int k=i;k<=j;k++) { cost[i][j]+=distant[k][mid]; } } } for(int i=1;i<=m;i++) { solve[i][1]=cost[1][i]; } for(int j=2;j<=n;j++) { for(int i=1;i<=m;i++) { solve[i][j]=2147283647; for(int k=j-1;k<=i;k++) { solve[i][j]=min(solve[i][j],solve[k][j-1]+cost[k+1][i]); } } } cout<<solve[m][n]; return 0; }