/*
LANG:C++
TASK:bus
*/
#include <iostream>
using namespace std;
int d[1001][1001];
int N,K;
int t[1001];
int opt[1001][1001];
int dp[1001][1001];

int ABS(int i)
	{
		if(i<0)
		 return -i;
		 else return i;
	}


int bsi(int i,int j,int k,int l)
	{
		if(i>j) return -1;
		int mid=(i+j)/2;
		int mid1=mid+1;
		int mid2=mid-1;
		if(d[mid][l]-d[mid][k-1]<=d[mid1][l]-d[mid1][k-1]&&d[mid][l]-d[mid][k-1]<=d[mid2][l]-d[mid2][k-1]) return mid;
		if(mid1<=l)
		if(d[mid][l]-d[mid][k-1]>=d[mid1][l]-d[mid1][k-1]) return bsi(mid1,j,k,l);
		if(mid2>=k)
		if(d[mid][l]-d[mid][k-1]>=d[mid2][l]-d[mid2][k-1]) return bsi(i,mid2,k,l);
	}
					



int main()
{
//	freopen("bus.txt","r",stdin);
//	freopen("bus1.txt","w",stdout);
	cin>>N>>K;
		int i;
			for(i=1;i<=N;i++)
				{
					cin>>t[i];
				}
			int j;
				for(i=1;i<=N;i++)
					{
						d[i][0]=0;
					for(j=1;j<=N;j++)
						{
							d[i][j]=d[i][j-1]+t[j]*ABS((j-i));
						}
					}
			for(i=1;i<=N;i++)
				for(j=1;j<=N;j++)
					{
						if(i>j) continue;
					//	cout<<bsi(i,j,i,j)<<" "<<i<<" "<<j<<endl;
						opt[i][j]=bsi(i,j,i,j);
					}
				for(i=1;i<=N;i++)
					for(j=1;j<=N;j++)
						{
							dp[i][j]=99999999;
						}
				for(i=1;i<=N;i++)
					{
						dp[i][1]=d[1][i];	
					//	cout<<dp[i][1]<<endl;		
					}
			int k;		
		//	cout<<N<<endl;
				for(i=2;i<=N;i++)
					for(j=2;j<=K-1;j++)
						{
							if(i==j) {dp[i][j]=0; continue;}
							if(i<j) continue;
						
							for(k=1;k<i;k++)
								{
									if(i-k<j) break;
								//	cout<<dp[i-k-1][j-1]+d[opt[i-k-1][i]][i]-d[opt[i-k-1][i]][i-k-1]<<" "<<i<<" "<<j<<" "<<k<<endl;						
												
										dp[i][j]=min(dp[i-k-1][j-1]+d[opt[i-k-1][i]][i]-d[opt[i-k-1][i]][i-k-1],dp[i][j]);
								}
						//	cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;	
						}
		int ans=99999999;				
		for(i=1;i<=N;i++)
			{	
		//		cout<<dp[i][K-1]<<" "<<d[N][N]-d[N][i]<<" "<<i<<endl;
				ans=min(dp[i][K-1]+(d[N][N]-d[N][i]),ans);
			}
			if(N>K)
			cout<<ans<<endl;
			else cout<<"0"<<endl;
//	cout<<opt[3][4]<<endl;																				
	//	cout<<d[6][7]-d[6][3]<<endl;
	
	return 0;
}
