import sys
from collections import deque
input = sys.stdin.readline
class linearFunc():
def __init__(self, a, b):
self.a = a
self.b = b
self.s = 0
self.num = 0
def intersect(L1, L2):
return (L2.b-L1.b)/(L1.a-L2.a)
N, K = map(int, input().split())
psum = list(map(int, input().split()))
#Prefix Sum
for i in range(1, N): psum[i] += psum[i-1]
#Initialize DP Table
prev = [[0]*N for _ in range(K)]
DP = [[0]*N for _ in range(2)]
for k in range(K):
F = [0]*N; F[0] = linearFunc(0, int(-1e14)); top = 1; idx = 0
for i in range(k+1, N):
g = linearFunc(psum[i-1], DP[(k%2)^1][i-1]-(psum[i-1])**2)
g.num = i-1
if F[top-1].a == g.a and F[top-1].b < g.b:
top -= 1
while top>0:
g.s = intersect(F[top-1], g)
if F[top-1].s < g.s: break
top -= 1
if g.s <= psum[-1]: F[top] = g; top += 1
elif F[top-1].a != g.a or (F[top-1].a == g.a and F[top-1].b < g.b):
while top>0:
g.s = intersect(F[top-1], g)
if F[top-1].s < g.s: break
top -= 1
F[top] = g; top += 1
X = psum[i]
while idx+1<top and F[idx+1].s < X: idx += 1
DP[k%2][i] = F[idx].a * X + F[idx].b
prev[k][i] = F[idx].num
print(DP[(K-1)%2][N-1])
temp = N-1; q = K-1; L = []
while q>=0:
L.append(prev[q][temp]+1)
temp = prev[q][temp]; q -= 1
L.sort()
print(' '.join(map(str, L)))
