///
/// ♪ Pizza mozzarella rella rella rella... ♪
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
const int N = 100'010;
const int K = 210;
ll dp[N][K];
ll sum[K], pro[K];
int pre[K];
ll a[N];
int n, k;
int main()
{
FAST;
cin >> n >> k;
Loop(i,0,n) cin >> a[i];
Loop(i,1,N) dp[i][0] = 1e15;
Loop(i,0,n)
{
Loop(j,1,K)
{
pro[j] += sum[j]*a[i], sum[j] += a[i];
while(pre[j] < i && dp[pre[j]][j-1] + pro[j] > dp[pre[j]+1][j-1] + (pro[j] - a[pre[j]]*(sum[j]-a[pre[j]])))
{
sum[j] -= a[pre[j]];
pro[j] -= a[pre[j]]*sum[j];
pre[j]++;
}
dp[i+1][j] = dp[pre[j]][j-1]+pro[j];
}
//Loop(j,1,k+1) cout << pre[j] << ' ';
//cout << '\n';
}
ll sum = 0, sum2 = 0;
Loop(i,0,n) sum += a[i], sum2 += a[i]*a[i];
cout << (sum*sum-sum2)/2 - dp[n][k+1] << '\n';
}
