Polycarp is practicing his problem solving skill. He has a list of n problems with difficulties a_1, a_2, ..., 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_{l ≤ i ≤ 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 ≤ k ≤ n ≤ 2000) — the number of problems and the number of days, respectively.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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, ..., t_k (t_1 + t_2 + ... + 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.
#winners never quit, quiters never win
from collections import deque as de
import math
from collections import Counter as cnt
class My_stack():
    def __init__(self):
        self.data = []
    def my_push(self, x):
        return (self.data.append(x))
    def my_pop(self):
        return (self.data.pop())
    def my_peak(self):
        return (self.data[-1])
    def my_contains(self, x):
        return (self.data.count(x))
    def my_show_all(self):
        return (self.data)
    def isEmpty(self):
      return len(self.data)==0

arrStack = My_stack()    
# A optimized school method based 
# Python3 program to check 
# if a number is prime 


def isPrime(n) : 

	# Corner cases 
	if (n <= 1) : 
		return False
	if (n <= 3) : 
		return True

	# This is checked so that we can skip 
	# middle five numbers in below loop 
	if (n % 2 == 0 or n % 3 == 0) : 
		return False

	i = 5
	while(i * i <= n) : 
		if (n % i == 0 or n % (i + 2) == 0) : 
			return False
		i = i + 6

	return True

def get_prime_factors(number):
    # create an empty list and later I will
    # run a for loop with range() function using the append() method to add elements to the list.
    prime_factors = []

    # First get the number of two's that divide number
    # i.e the number of 2's that are in the factors
    while number % 2 == 0:
        prime_factors.append(2)
        number = number / 2

    # After the above while loop, when number has been
    # divided by all the 2's - so the number must be odd at this point
    # Otherwise it would be perfectly divisible by 2 another time
    # so now that its odd I can skip 2 ( i = i + 2) for each increment
    for i in range(3, int(math.sqrt(number)) + 1, 2):
        while number % i == 0:
            prime_factors.append(int(i))
            number = number / i


    # Here is the crucial part.
    # First quick refreshment on the two key mathematical conjectures of Prime factorization of any non-Prime number
    # Which is - 1. If n is not a prime number AT-LEAST one Prime factor would be less than sqrt(n)
    # And - 2. If n is not a prime number - There can be AT-MOST 1 prime factor of n greater than sqrt(n).
    # Like 7 is a prime-factor for 14 which is greater than sqrt(14)
    # But if the above loop DOES NOT go beyond square root of the initial n.
    # Then how does that greater than sqrt(n) prime-factor
    # will be captured in my prime factorization function.
    # ANS to that is - in my first for-loop I am dividing n with the prime number if that prime is a factor of n.
    # Meaning, after this first for-loop gets executed completely, the adjusted initial n should become
    # either 1 or greater than 1
    # And if n has NOT become 1 after the previous for-loop, that means that
    # The remaining n is that prime factor which is greater that the square root of initial n.
    # And that's why in the next part of my algorithm, I need to check whether n becomes 1 or not,
    #This code is taken by rohan paul's github
    if number > 2:
        prime_factors.append(int(number))

    return prime_factors
def get_frequency(list):
    dic={}
    for ele in list:
        if ele in dic:
            dic[ele] += 1
        else:
            dic[ele] = 1
    return dic
#here we go......................
#winners never quit, quitters never win
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=sorted(a, reverse=True)
dic={}
totalprofit=0
for i in range(k):
    totalprofit+=l[i]
    if l[i] in dic:
        dic[l[i]]+=1
    else:
        dic[l[i]]=1
ans=[]
count=0
for i in range(n):
    if a[i] in dic:
        count+=1
        if dic[a[i]]==1:
            del dic[a[i]]
        else:
            dic[a[i]]-=1
        if not dic:
            count-=1
            ans.append(count+ n-i)
            break
        else:
            ans.append(count)
        count=0
    else:
        count+=1
print(totalprofit)
print(*ans) 

