#include <iostream>
#include <cstdio>
using namespace std;
const int NMAX = 1e5 + 5, KMAX = 2e2 + 5;
const long long INF = 1LL * 1e18;
int N, K;
int sp[NMAX];
long long ans, dp[NMAX][2];
int Keep[NMAX][KMAX];
int V[KMAX];
namespace InParser
{
static const int BSIZE = (1 << 16);
static int pos = BSIZE - 1;
static char buff[BSIZE];
static inline char Char ()
{
++pos;
if(pos == BSIZE)
{
pos = 0;
int n = fread(buff, 1, BSIZE, stdin);
if(n != BSIZE)
for(int i = n; i < BSIZE; ++i)
buff[i] = 0;
}
return buff[pos];
}
inline int Int ()
{
int ans = 0;
for( ; ; )
{
char Ch = Char();
if(Ch >= '0' && Ch <= '9')
{
ans = (int)(Ch - '0');
break;
}
}
for( ; ; )
{
char Ch = Char();
if(Ch >= '0' && Ch <= '9')
ans = ans * 10 + (int)(Ch - '0');
else
break;
}
return ans;
}
};
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
/// freopen("sequence.in", "r", stdin);
/// freopen("sequence.out", "w", stdout);
N = InParser :: Int(), K = InParser :: Int();
for(int i = 1; i <= N; ++i)
{
int A = InParser :: Int();
sp[i] = sp[i - 1] + A;
}
return;
}
static inline int Query (int Left, int Right)
{
if(Left > Right)
return 0;
return sp[Right] - sp[(Left - 1)];
}
static inline long long Cost (int Left, int Right)
{
if(Left > Right)
return 0;
int s = Query(Left, Right);
return (1LL * s * s);
}
static inline void Load ()
{
ans = Cost(1, N);
return;
}
static inline int MIN (int a, int b)
{
return ((a < b) ? a : b);
}
static inline void Go (int Left, int Right, int Chosen_Left, int Chosen_Right, int Level)
{
if(Left > Right)
return;
int Mid = ((Left + Right) >> 1);
int Chosen = Mid;
for(int k = Chosen_Left; k <= MIN(Mid, Chosen_Right); ++k)
{
long long Now = dp[k - 1][((Level - 1) & 1)] + Cost(k, Mid);
if(Now < dp[Mid][(Level & 1)])
dp[Mid][(Level & 1)] = Now, Chosen = k;
}
Keep[Mid][Level] = Chosen;
Go(Left, Mid - 1, Chosen_Left, Chosen, Level);
Go(Mid + 1, Right, Chosen, Chosen_Right, Level);
return;
}
static inline void Initialize ()
{
for(int i = 0; i <= N; ++i)
for(int j = 0; j < (2 - (K == 1)); ++j)
dp[i][j] = INF;
for(int i = 1; i <= N; ++i)
dp[i][1] = Cost(1, i);
for(int i = 1; i <= N; ++i)
Keep[i][1] = i;
return;
}
static inline void Write ()
{
int pos = N;
for(int i = (K + 1); i > 1; --i)
pos = V[i - 1] = Keep[pos][i] - 1;
for(int i = 1; i <= K; ++i)
{
printf("%d", V[i]);
if(i != K)
printf(" ");
}
printf("\n");
return;
}
static inline void Solve ()
{
Initialize();
for(int j = 2; j <= (K + 1); ++j)
Go(j, N, j, N, j);
ans -= 1LL * dp[N][((K + 1) & 1)];
ans >>= 1LL;
printf("%lld\n", ans);
Write();
return;
}
int main()
{
Read();
Load();
Solve();
return 0;
}
