#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/
//Note to self: Check for overflow
#define int li
int a[100005];
li dp[100005][202];
int gde[100005][202];
int pre[100005];
li cost(int l, int r)
{
return (li)pre[l-1]*(pre[r]-pre[l-1]);
}
void rekurz(int n, int k)
{
if (k==0) return;
rekurz(gde[n][k],k-1),cout<<max(1ll,gde[n][k])<<" ";
}
int k=1;
vector<pair<pli,int>> len[271828];
vector<ld> presek[271828];
int l[271828],r[271828];
ld preseci(pli a, pli b)
{
return (ld)(b.yy-a.yy)/(a.xx-b.xx);
}
void try_add(int i, pair<pli,int> a)
{
if (presek[i].empty()) presek[i].pb(-1e18),len[i].pb(a);
else
{
if (a.xx.xx==len[i].back().xx.xx) return;
ld p=preseci(a.xx,len[i].back().xx);
while (p<=presek[i].back()) presek[i].popb(),len[i].popb();
len[i].pb(a),presek[i].pb(p);
}
}
void merge(int i)
{
int aa=0,bb=0;
while (true)
{
bool gde=0;
if (aa==presek[2*i].size())
{
if (bb==presek[2*i+1].size()) break;
gde=1;
}
else if (bb==presek[2*i+1].size()) gde=0;
else gde=(len[2*i+1][bb].xx<len[2*i][aa].xx || (len[2*i+1][bb].xx==len[2*i][aa].xx && len[2*i+1][bb].yy>len[2*i][aa].yy));
if (gde) try_add(i,len[2*i+1][bb++]);
else try_add(i,len[2*i][aa++]);
}
}
pli qry(int p, li x)
{
int bs=lower_bound(all(presek[p]),x)-presek[p].begin()-1;
return {len[p][bs].xx.xx*x+len[p][bs].xx.yy,len[p][bs].yy};
}
pli qry(int p, int ll, int rr, li x)
{
if (ll>r[p] || rr<l[p]) return {-1e18,-1};
if (ll<=l[p] && rr>=r[p]) return qry(p,x);
return max(qry(2*p,ll,rr,x),qry(2*p+1,ll,rr,x));
}
void ispisi()
{
for (int kk=1;kk<=k;kk*=2)
{
ff(i,kk,2*kk)
{
ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
cout<<"; ";
} cout<<endl;
} cout<<endl;
}
main()
{
FAST;
int n,m; cin>>n>>m;
fff(i,1,n) cin>>a[i];
fff(i,1,n) pre[i]=pre[i-1]+a[i];
while (k<=n) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
fff(j,1,m)
{
if (n>1000)
{
ff(i,1,2*k) len[i].clear(),presek[i].clear();
fff(i,1,n) len[i+k].pb({{pre[i],dp[i][j-1]-pre[i]*pre[i]},i}),presek[i+k].pb({-1e18});
bff(i,1,k) merge(i);
//ispisi();
fff(i,2,n)
{
pli tmp=qry(1,1,i-1,pre[i]);
dp[i][j]=tmp.xx,gde[i][j]=tmp.yy;
}
}
else
{
fff(i,2,n) ff(g,1,i)
{
li sta=dp[g][j-1]+cost(g+1,i);
if (sta>=dp[i][j]) dp[i][j]=sta,gde[i][j]=g;
}
}
}
/*fff(j,1,m)
{
fff(i,1,n) cout<<dp[i][j]<<" ";
cout<<endl;
} cout<<endl;*/
cout<<dp[n][m]<<"\n";
rekurz(n,m);
/*int n; cin>>n;
while (k<n) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,0,n)
{
int nn,kk; cin>>nn>>kk;
len[i+k].pb({nn,kk});
presek[i+k].pb({-1e18});
}
bff(i,1,k) merge(i);
ispisi();
while (true)
{
int ll,rr,x; cin>>ll>>rr>>x; ll--,rr--;
cout<<qry(1,ll,rr,x)<<endl;
}*/
}
//Note to self: Check for overflow
/*
7 3
4 1 3 4 0 2 3
7 6
4 1 3 4 0 2 3
4
-1 0
1 0
0 1
0 2
*/
