// 有显然贡献的结论。
// 斜率优化 dp 即可。
// 要记得记录过程。
// 至于分治决策单调性什么的还是想多了……估计跑不过去。

#include <algorithm>
#include <deque>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
llt S[100005],Last[100005],Ans[100005];uint AnsP[205][100005];
uint n;
voi doit(llt*Last,llt*Ans,uint*AnsP)
{
    typedef std::pair<llt,llt>Line;
    Ans[0]=-1e18,AnsP[0]=-1;
    std::deque<std::pair<Line,uint> >D{{{0,Last[0]},0}};
    auto val=[](Line L,llt v){return L.first*v+L.second;};
    for(uint i=1;i<=n;i++)
    {
        while(D.size()>1&&val(D[0].first,S[i])<=val(D[1].first,S[i]))D.pop_front();
        Ans[i]=val(D[0].first,S[i]),AnsP[i]=D[0].second;
        Line L{S[i],Last[i]-S[i]*S[i]};
        while(D.size()&&D.back().first.first==L.first&&D.back().first.second<=L.second)D.pop_back();
        if(D.size()&&D.back().first.first==L.first)continue;
        while(D.size()>1)
        {
            Line L1=D.back().first,L2=D[D.size()-2].first;
            if((L2.second-L.second)*(L2.first-L1.first)>=(L2.second-L1.second)*(L2.first-L.first))D.pop_back();
            else break;
        }
        D.push_back({L,i});
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    Ans[0]=-1e18,AnsP[0][0]=-1;
    uint k;scanf("%u%u",&n,&k);
    for(uint i=1;i<=n;i++)scanf("%lld",S+i),S[i]+=S[i-1];
    for(uint i=1;i<=k;i++)
    {
        for(uint j=0;j<=n;j++)Last[j]=Ans[j],Ans[j]=0;
        doit(Last,Ans,AnsP[i]);
    }
    printf("%lld\n",Ans[n]);
    for(uint i=k,p=n;i;i--)printf("%u%c",AnsP[i][p]," \n"[i==1]),p=AnsP[i][p];
    return 0;
}