Polycarp is practicing his problem solving skill. He has a list of $n$ problems with difficulties $a_1, a_2, \dots, a_n$, respectively. His plan is to practice for exactly $k$ days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all $n$ problems in exactly $k$ days.

Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can't skip problems or solve them multiple times. As a result, in $k$ days he will solve all the $n$ problems.

The profit of the $j$-th day of Polycarp's practice is the maximum among all the difficulties of problems Polycarp solves during the $j$-th day (i.e. if he solves problems with indices from $l$ to $r$ during a day, then the profit of the day is $\max\limits_{l \le i \le r}a_i$). The total profit of his practice is the sum of the profits over all $k$ days of his practice.

You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all $n$ problems between $k$ days satisfying the conditions above in such a way, that the total profit is maximum.

For example, if $n = 8, k = 3$ and $a = [5, 4, 2, 6, 5, 1, 9, 2]$, one of the possible distributions with maximum total profit is: $[5, 4, 2], [6, 5], [1, 9, 2]$. Here the total profit equals $5 + 6 + 9 = 20$.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of problems and the number of days, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$) — difficulties of problems in Polycarp's list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).


-----Output-----

In the first line of the output print the maximum possible total profit.

In the second line print exactly $k$ positive integers $t_1, t_2, \dots, t_k$ ($t_1 + t_2 + \dots + t_k$ must equal $n$), where $t_j$ means the number of problems Polycarp will solve during the $j$-th day in order to achieve the maximum possible total profit of his practice.

If there are many possible answers, you may print any of them.


-----Examples-----
Input
8 3
5 4 2 6 5 1 9 2

Output
20
3 2 3
Input
5 1
1 1 1 1 1

Output
1
5

Input
4 2
1 2000 2000 2

Output
4000
2 2



-----Note-----

The first example is described in the problem statement.

In the second example there is only one possible distribution.

In the third example the best answer is to distribute problems in the following way: $[1, 2000], [2000, 2]$. The total profit of this distribution is $2000 + 2000 = 4000$.

Difficulty: introductory

Starter code:

Solutions:

def mi():
	return map(int, input().split())

n, k = mi()
a = list(mi())
for i in range(n):
	a[i] = [a[i],i]

a.sort(reverse= True)

a = a[:k]
s = 0
ind = []
for i in a:
	s+=i[0]
	ind.append(i[1])
ind.sort()
for i in range(k):
	ind[i]+=1
ind1 = ind.copy()
for i in range(1,len(ind)):
	ind[i]-=ind1[i-1]
ind[-1] = n-sum(ind[:k-1])
print (s)
for i in ind:
	print (i, end = ' ')

n,k = map(int,input().split())
l = list(map(int,input().split()))

l = sorted([(x,i) for i,x in enumerate(l)],key = lambda x: (x[0],x[1]))
used = l[-k:]

s = sum(x[0] for x in used)
days = sorted(x[1] for x in used)
print (s)

d = []
t = 0
for x in days[:-1]:
    d.append(x-t + 1)
    t = x + 1
d.append(n-t)
print (*d)

import sys
import io

stream_enable = 0

inpstream = """

"""

if stream_enable:
    sys.stdin = io.StringIO(inpstream)
    input()

def inpmap():
    return list(map(int, input().split()))

n, k = inpmap()
arr = inpmap()
ar = arr[:]
ar.sort()
b = ar[-k:]
print(sum(b))
m = 0
r = []
for i, x in enumerate(arr):
    if x in b:
        b.remove(x)
        r.append(i - m + 1)
        m = i + 1
r[-1] += n - m
print(*r)


n, k = map(int, input().split())
a=sorted(enumerate(map(int, input().split())), key=lambda x:-x[1])[:k]
s=0
for i in a:
    s+=i[1]
a.sort(key=lambda x:x[0])
print(s)
prev=-1
for i in a[:-1]:
    print(i[0]-prev, end=' ')
    prev=i[0]
print(n-prev-1)


import heapq

n,k = map(int, input().split())
a = list(enumerate(map(int, input().split()), 1))
s = heapq.nlargest(k, a, key = lambda x: x[1])
su = sum([si[1] for si in s])
s = sorted([si[0] for si in s])
s[-1] = n
for i in range(len(s)-1, 0, -1):
    s[i] -= s[i-1]

print(su)
print(*s)

problems, days = list(map(int, input().split(" ")))
difficulties = list(map(int, input().split(" ")))

copyDifficulties = difficulties.copy()
copyDifficulties.sort()
maxValues = {}

for i in range(days):
    if copyDifficulties[problems - 1 - i] in maxValues:
        maxValues[copyDifficulties[problems - i - 1]] += 1
    else:
        maxValues[copyDifficulties[problems - i - 1]] = 1

gained = 0
solved = []
solvedDay = 0
for i in range(problems):
    solvedDay += 1
    if difficulties[i] in maxValues and maxValues.get(difficulties[i]) >= 1:
        gained += difficulties[i]
        maxValues[difficulties[i]] -= 1
        solved.append(solvedDay)
        solvedDay = 0
solved[len(solved) - 1] += problems - sum(solved)
print(gained)
res = " "
for i in solved:
    res += str(i) + " "
print(res.strip())


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 3000

for i in range(n):
    a[i] = (i, a[i])

a.sort(key=lambda x: x[1], reverse=True)

for i in range(k):
    b[a[i][0]] = 1

cur = 0
ans = []
total = 0
addtolast = 0
a.sort(key=lambda x: x[0])

for i in range(n):
    if b[i] == 1:
        total += a[i][1]
        ans.append(i - cur + 1)
        addtolast = n - i - 1
        cur = i + 1

ans[-1] += addtolast

print(total)
print(*ans)

n, m = map(int, input().split())
ls = [int(i) for i in input().split()]

t = sorted(ls)
t.reverse()
ans = 0
st = []
for i in range(m):
    ans += t[i]
    st.append(t[i])

print(ans)

l = -1
for i in range(n):
    if ls[i] in st:
        if len(st) == 1:
            print(n - 1 - l);return

        st.pop(st.index(ls[i]))
        print(i - l, end=' ')
        l = i



length, k = map(int, input().split())

problems = list(enumerate(map(int, input().split(' '))))

problems.sort(key=lambda i: i[1], reverse=True)

maxs = problems[:k]

maxs.sort()

distr = []

prev = -1
total = 0
for i in range(k):
    distr.append(maxs[i][0] - prev)
    prev = maxs[i][0]
    total += distr[-1]

distr[-1] += length - total

print(sum(map(lambda i: i[1], maxs)))
print(*distr)

n, k = list(map(int, input().split(" ")))

numbers = [int(i) for i in input().split(" ")]
numbers = [(num, i + 1) for i, num in enumerate(numbers)]

numbers = sorted(numbers)
numbers = numbers[::-1][:k]
indices = [i[1] for i in numbers]
indices = sorted(indices)

for i in range(k -1, 0, -1):
    indices[i] -= indices[i - 1]

s = sum(indices)
indices[-1] += n - s
print(sum([i[0] for i in numbers]))
print(*indices)


R = lambda: map(int, input().split())

n, k = R()
a = list(R())
b = sorted(a)
b = b[n-k:]
ans = []

print(sum(b))

k = 0
for t in a:
    k += 1
    if t in b:
        del b[b.index(t)]
        ans.append(k)
        k = 0
if k:
    ans[-1] += k

print(*ans, sep=' ')

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

need = sorted(a, reverse=True)

ind = list()
for el in need[:k]:
    ind.append(a.index(el))
    a[a.index(el)] = 0

ind.sort()

print(sum(need[:k]))

ind[-1] = n - 1
ind.insert(0, -1)
ans = [el - ind[i] for i, el in enumerate(ind[1:])]

print(' '.join(map(str, ans)))


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
b = b[:k]
s = sum(b)
rec = []
k = 1
for i in range(n):
    if a[i] not in b:
        k += 1
        continue
    else:
        b.remove(a[i])
        rec.append(k)
        k = 1

rec[-1] += n - sum(rec)
print(s)
print(" ".join(map(str, rec)))

n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))

res = sorted(a, reverse = True)
res = res[0:k]
print(sum(res))
s = res
prev = 0
counter = 1
for i in range(len(a)):
	if a[i] in s:
		s.pop(s.index(a[i]))
		if counter == k:
			print(n - prev)
		else:
			print(i + 1 - prev, end=' ')
		counter += 1
		prev = i + 1


n, k = list(map(int, input().split()))

a = list(map(int, input().split()))

at = []

z = 0
for i in a:
    at.append( (z, i) )
    z = z + 1

at.sort(key = lambda x:-x[1])

zt = sorted(at[:k], key = lambda x:x[0])

prev = -1
ai = []
suma = 0
for i in zt:
    ai.append(i[0] - prev)
    prev = i[0]
    suma += i[1]


ai[-1] = ai[-1] + (n - sum(ai))

print(suma)
print(" ".join(str(i) for i in ai))


n, k  =map(int,input().split())

data = list(map(int,input().split()))


an_data = [(data[i],i ) for i in range(n)]

an_data.sort(key = lambda x:x[0])
an_data = an_data[::-1]
ans = 0
answer = []
for i in range(k):
    ans += an_data[i][0]
    answer.append(an_data[i][1])


print(ans)

prev = 0
answer.sort()

for i in range(k):
    el = answer[i]
    if i == k - 1:
        print(n - prev)
        break
    
    if prev == 0:
        print(el  + 1 ,end=" ")
        prev = el  +1
        continue
        
    print(el - prev  +1, end = " ")
    prev = el  + 1


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append((a[i], i))
b.sort(reverse=True)
sum = 0
lol = [-1]
for i in range(k):
    sum += b[i][0]
    lol.append(b[i][1])
lol.sort()
ans = []
for i in range(1, k + 1):
    ans.append(lol[i] - lol[i - 1])
ans[k - 1] += n - 1 - lol[k]
print(sum)
print(*ans)

# from collections import Counter as cc
n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = sorted(zip(arr, list(range(n))), reverse=True)
s = s[:k]
print(sum(x for x, _ in s))
s.sort(key=lambda x: x[1])
prev = -1
ans = []
for x, i in s[:-1]:
    n -= i - prev
    ans.append(i - prev)
    prev = i
ans.append(n)
print(*ans)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = sorted(a)[-k:]
print(sum(b))
used = [0 for i in range(n)]
for elem in b:
    for i in range(n):
        if a[i] == elem and used[i] == 0:
            used[i] = 1
            break
last = 0
count = 0
ans = []
for i in range(n):
    if used[i]:
        ans.append(i - last + 1)
        last = i + 1
        count += 1
    if count == k:
        ans.pop()
        ans.append(n - sum(ans))
print(*ans)


#codeforces_1006_B
n,k = [ int(e) for e in input().split(" ") ]
L = [ int(e) for e in input().split(" ") ]
M = L[:]
M.sort()
M = M[-1:-k-1:-1]
cursor = 0
print(sum(M))
for e in L:
    cursor += 1
    if e in M:
        M.remove(e)
        if M != []:
            print(cursor,end=" ")
            cursor = 0
        else:
            pass;
print(cursor)

n, k = map(int, input().split())
s = [int(elem) for elem in input().split()]
anses = []
s2 = s[:]
s2.sort(reverse = True)
s2 = s2[:k]
ans = sum(s2)
arr = []
e = 0
for i in range(n):
    if s[i] in s2:
        anses.append(str(i - e + 1))
        e = i + 1
        b = s2.index(s[i])
        del s2[b]
if e - 1 < n:
    anses[len(anses) - 1] = str(int(anses[len(anses) - 1]) + n - e)
print(ans)
print(' '.join(anses))

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
# print(b)
b = b[:k]
b.sort( key = lambda x : x[1])
# print(b)
ans = 0
for i in b:
    ans += i[0]
print(ans)
prev = 0
for iter, i  in enumerate(b):
    if iter != len(b) - 1:
        print(i[1] + 1 - prev, end = ' ')
        prev = i[1] + 1
    else:
        print(n - prev)

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [i for i in a]
a.sort()
d = {}
count = 0
ans = []
ans_sum = 0
for i in range(n):
    if not b[i] in d:
        d[b[i]] = []
    d[b[i]].append(i)

for i in reversed(range(n)):
    ans_sum += a[i]
    ans.append(d[a[i]][0])
    d[a[i]] = d[a[i]][1:]
    count += 1
    if count == k:
        break

print(ans_sum)
ans.sort()
ans = [-1] + ans
l = len(ans)
for i in range(1, l - 1):
    print(ans[i] - ans[i - 1], end = " ")
print(n - ans[-2] - 1)

n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(n):
    q.append(a[i])
q.sort()
q = q[(-m):]
s = 0
for i in range(m):
    s += q[i]
print(s)
s = 1
w = []
f = 1
for i in range(n):
    if(a[0] in q):
        w.append(s)
        f+=s
        s = 0
        q.remove(a[0])
    a.remove(a[0])
    s+=1
w[-1] += n-f+1
for i in range(m):
    print(w[i], end = " ")