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 = deque(); F.append(linearFunc(0, int(-1e14)))
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[-1].a == g.a and F[-1].b < g.b:
F.pop()
while F:
g.s = intersect(F[-1], g)
if F[-1].s < g.s: break
F.pop()
if g.s <= psum[-1]: F.append(g)
elif F[-1].a != g.a or (F[-1].a == g.a and F[-1].b < g.b):
while F:
g.s = intersect(F[-1], g)
if F[-1].s < g.s: break
F.pop()
F.append(g)
X = psum[i]
while len(F)>1 and F[1].s < X: F.popleft()
DP[k%2][i] = F[0].a * X + F[0].b
prev[k][i] = F[0].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)))
