#include <bits/stdc++.h>
using namespace std;
long long dp[100005][2], a[100005], b[100005];
vector<long long> vec;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, k;
cin >> n >> k;
for (long long i=1; i<=n; i++)
{
cin >> a[i];
b[i]=b[i-1]+a[i];
}
for (long long i=1; i<=k+1; i++)
{
vec.clear();
vec.push_back(i-1);
long long ii=i&1, iii=(i&1)^1, sz=1;
for (long long j=i; j<=n; j++)
{
// cout << "i j " << i << ' ' << j << '\n';
if (sz>=2)
{
long long x=vec[sz-2], y=vec[sz-1];
while (dp[y][iii]-dp[x][iii]<=(b[n]-b[j])*(b[y]-b[x]))
{
vec.pop_back();
sz--;
// cout << "vec pop back, now only have " << sz << '\n';
if (sz<2)
break;
x=vec[sz-2];
y=vec[sz-1];
}
}
dp[j][ii]=dp[vec[sz-1]][iii]+(b[n]-b[j])*(b[j]-b[vec[sz-1]]);
if (sz>=2)
{
long long x=vec[sz-2], y=vec[sz-1];
while ((dp[y][iii]-dp[x][iii])*(b[j]-b[y])<(dp[j][iii]-dp[y][iii])*(b[y]-b[x]))
{
vec.pop_back();
sz--;
// cout << "vec pop back, now only have " << sz << '\n';
if (sz<2)
break;
x=vec[sz-2];
y=vec[sz-1];
}
}
sz++;
vec.push_back(j);
// cout << "vec push back " << j << ", now have " << sz << '\n';
}
}
cout << dp[n][(k+1)&1];
return 0;
}
