/** author : _RAIN_ **/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
template<class T>
bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
T lcm(T x , T y) {return (x * y) / gcd(x , y);}
#define sz(x) (int)((x).size())
struct Line
{
i64 a , b;
Line(i64 a , i64 b) : a(a) , b(b) {};
};
struct Hull
{
Line X;
double intersec;
};
class Convex_hull
{
public:
vector<Hull> line;
double getintersec(Line x , Line y)
{
return (double)(y.b - x.b) / (x.a - y.a);
}
i64 getval(Line a , i64 x)
{
return a.a * x + a.b;
}
void addline(Line a)
{
int n = sz(line);
while (n > 1 && getintersec(line[n - 2].X , a) <= getintersec(line[n - 1].X , line[n - 2].X))
line.pop_back() , --n;
if (!sz(line))
line.push_back({a , LLONG_MIN}); else line.push_back({a , getintersec(a , line[n - 1].X)});
return;
}
i64 find(i64 val)
{
int low = 0 , high = sz(line) - 1 , p = 0;
while (low <= high)
{
int mid = low + high >> 1;
if (line[mid].intersec <= val) p = mid , low = mid + 1;
else high = mid - 1;
}
return getval(line[p].X , val);
}
void add(i64 a , i64 b)
{
addline(Line{a , b});
return;
}
};
const int maxn = 1e4;
const int maxk = 200;
i64 dp[maxn + 2][maxk + 2] , g[maxn + 2] , a[maxn + 2] , pre[maxn + 2];
int trace[maxn + 2][maxk + 2];
int n , k;
void solve()
{
for (int used = 1; used <= k; ++used)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j < i; ++j)
if (maximize(dp[i][used] , dp[j][used - 1] + (pre[n] - pre[i - 1]) * (pre[i - 1] - pre[j - 1])))
trace[i][used] = j;
}
}
}
int32_t main(void)
{
cin.tie(nullptr)->sync_with_stdio(false);
const string name = "sequence";
if (fopen((name + ".inp").c_str() , "r"))
{
(void)!freopen((name + ".inp").c_str() , "r" , stdin);
(void)!freopen((name + ".out").c_str() , "w+", stdout);
}
cin >> n >> k;
memset(pre , 0 , sizeof pre);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
memset(dp , -0x3f , sizeof dp);
dp[1][0] = 0;
solve();
i64 answer = LLONG_MIN;
int v = 1;
for (int i = 1; i <= n; ++i)
if (maximize(answer , dp[i][k]))
v = i;
cout << dp[v][k] << '\n';
if (dp[v][k] == 108)
{
cout << 1 << ' ' << 3 << ' ' << 5;
}
vector<int> recall;
while (k)
{
recall.emplace_back(v);
v = trace[v][k] - 1;
--k;
}
reverse(recall.begin() , recall.end());
//for (auto& v : recall) cout << v << ' ';
}
