import sys
from collections import deque
input = sys.stdin.readline
def intersect(L1, L2):
return (L2[1]-L1[1])/(L1[0]-L2[0])
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((0, int(-1e14), -1, -1))
for i in range(k+1, N):
g = (psum[i-1], DP[(k%2)^1][i-1]-psum[i-1]*psum[i-1], 0, i-1)
if F[-1][0] == g[0] and F[-1][1] < g[1]:
F.pop()
while F:
g = (g[0], g[1], intersect(F[-1], g), g[3])
if F[-1][2] < g[2]: break
F.pop()
F.append(g)
elif F[-1][0] != g[0] or (F[-1][0] == g[0] and F[-1][1] < g[1]):
while F:
g = (g[0], g[1], intersect(F[-1], g), g[3])
if F[-1][2] < g[2]: break
F.pop()
F.append(g)
X = psum[i]
while len(F)>1 and F[1][2] < X: F.popleft()
DP[k%2][i] = F[0][0] * X + F[0][1]
prev[k][i] = F[0][3]
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)))
