#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 3005;

int n, m, dis[N], dp[N][N];
int head, tail, Q[N];

int calc(int i, int j){ return m * dis[j] * dis[j] + dp[i - 1][j]; }

signed main(){
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &dis[i]), dis[i] += dis[i - 1];
	for(int i = 1; i <= n; i++) dp[1][i] = m * dis[i] * dis[i];
	for(int i = 2; i <= m; i++){
		head = tail = 1; Q[1] = 0;
		for(int j = 1; j <= n; j++){
			while(head < tail && calc(i, Q[head + 1]) - calc(i, Q[head])
							 < 2 * m * dis[j] * (dis[Q[head + 1]] - dis[Q[head]]))
				head++;
			cout << Q[head] << ' ' << Q[tail] << ' ' << head << ' ' << tail << endl;
			dp[i][j] = dp[i - 1][Q[head]] + m * (dis[j] - dis[Q[head]]) * (dis[j] - dis[Q[head]]);
			while(head < tail && (calc(i, Q[tail]) - calc(i, Q[tail - 1]) * (dis[j] - dis[tail]))
							>= (calc(i, j) - calc(i, Q[tail])) * (dis[Q[tail]] - dis[Q[tail - 1]]))
				tail--;
			Q[++tail] = j;
		}
	}
	
	printf("%lld\n", dp[m][n] - dis[n] * dis[n]);
	exit(0);
}