#include <bits/stdc++.h>
#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 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--)
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;
//Note to self: Check for overflow
#define int li
int a[100005];
li dp[100005][2]; //preth i cur
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];
bool cur=0;
fff(j,1,m)
{
cur=!cur;
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][!cur]-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][cur]=tmp.xx,gde[i][j]=tmp.yy;
}
}
else
{
fff(i,2,n) ff(g,1,i)
{
li sta=dp[g][!cur]+cost(g+1,i);
if (sta>=dp[i][cur]) dp[i][cur]=sta,gde[i][j]=g;
}
}
}
/*fff(j,1,m)
{
fff(i,1,n) cout<<dp[i][j]<<" ";
cout<<endl;
} cout<<endl;*/
cout<<dp[n][cur]<<"\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
*/
