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.
                            /* Rajkin Hossain */
import java.io.*;
import java.util.*;

public class C {

    //static FastInput k = new FastInput("/home/rajkin/Desktop/input.txt");
    static FastInput k = new FastInput(System.in);
    static FastOutput z = new FastOutput();
    static PriorityQueue<PairIndex> indexes;
    static PriorityQueue<PairValue> values;
    static ArrayList<Integer> ans;
    static int n, kk;
       
    static void startAlgorithm() {
    	int i = 0;
    	int j = 0;
    	long sum = 0;
    	int prevI = 0;
    	
    	while(!indexes.isEmpty()) {
    		PairIndex pIndex = indexes.poll();
    		while(pIndex.index != j) {
    			j++;
    		}
    		
    		sum += pIndex.value;
    		ans.add(j-i+1);
    		 
    		prevI = i;
    		i = j + 1;
    		j++;
    	}
    	
    	if(j != n) {
    		ans.remove(ans.size() - 1);
    		ans.add((n-1) - prevI + 1);
    	}
    	
    	z.println(sum);
    	for(int ii = 0; ii<ans.size(); ii++) {
    		z.print(ans.get(ii)+" ");
    	}
    	
    	z.println();
    }
	
	static void getInputsAndInitializes() {
		indexes = new PriorityQueue<PairIndex>();
		values = new PriorityQueue<PairValue>();
		ans = new ArrayList<Integer>();
		
		n = k.nextInt();
		kk = k.nextInt();
		
		for(int i = 0; i<n ; i++) {
			values.add(new PairValue(i, k.nextInt()));
		}
		
    	for(int i = 0; i<kk ; i++) {
    		PairValue pValue = values.poll();
    		indexes.add(new PairIndex(pValue.index, pValue.value));
    	}
    }
    
	public static void main(String [] args) throws FileNotFoundException {        
		while(k.hasNext()) {
        	getInputsAndInitializes();
        	startAlgorithm();
        }
        z.flush();
        System.exit(0);
	}
	
	
	/* MARK: Pair implementation */
	
	public static class Pair{
		int i, j;
		public Pair(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
	
	
	public static class PairIndex implements Comparable<PairIndex> {
		int index, value;
		public PairIndex(int index, int value) {
			this.index = index;
			this.value = value;
		}
		
		@Override
		public int compareTo(PairIndex p) {
			// TODO Auto-generated method stub
			return this.index - p.index;
		}
	}
	
	public static class PairValue implements Comparable<PairValue> {
		int index, value;
		public PairValue(int index, int value) {
			this.index = index;
			this.value = value;
		}
		
		@Override
		public int compareTo(PairValue p) {
			// TODO Auto-generated method stub
			return p.value - this.value;
		}
	}
	
	
	/* MARK: SetBit implementation */
	
	public static long setBit(long pos, long value) {
		return value |= (1l << pos);
	}
	
    /* MARK: FastInput and FastOutput implementation */
	 
    public static class FastInput {
        BufferedReader reader;
        StringTokenizer tokenizer;
 
        public FastInput(InputStream stream){
            reader = new BufferedReader(new InputStreamReader(stream));
        }
        
	    public FastInput(String path){
	        try {
	        	reader = new BufferedReader(new FileReader(path));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	        tokenizer = null;
	    }
 
        public String next() {
            return nextToken();
        }
        
        public String nextLine() {
            try {
				return reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
            
            return null;
        }
 
        public boolean hasNext(){
            try {
                return reader.ready();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return false;
        }
 
        public String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String line = null;
                try {
                    line = reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                tokenizer = new StringTokenizer(line);
            }
            return tokenizer.nextToken();
        }
 
        public Integer nextInt() {
            return Integer.parseInt(nextToken());
        }
       
        public Long nextLong() {
            return Long.valueOf(nextToken());
        }
    	
    	public void inputIntegerList(ArrayList<Integer> list, int size) {
    		for(int i = 0; i<size; i++) {
    			list.add(nextInt());
    		}
    	}
    	
    	public void inputLongList(ArrayList<Long> list, int size) {
    		for(int i = 0; i<size; i++) {
    			list.add(nextLong());
    		}
    	}
    	
    	public void inputWordList(ArrayList<String> list, int size) {
    		for(int i = 0; i<size; i++) {
    			list.add(next());
    		}
    	}
    	
    	public void inputLineList(ArrayList<String> list, int size) {
    		for(int i = 0; i<size; i++) {
    			list.add(nextLine());
    		}
    	}
    	
    	public void inputIntegerArray(int [] array, int size) {
    		for(int i = 0; i<size; i++) {
    			array[i] = nextInt();
    		}
    	}

    	public void inputLongArray(long [] array, int size) {
    		for(int i = 0; i<size; i++) {
    			array[i] = nextLong();
    		}
    	}
    	
    	public void inputWordArray(String [] array, int size) {
    		for(int i = 0; i<size; i++) {
    			array[i] = next();
    		}
    	}
    	
    	public void inputLineArray(String [] array, int size) {
    		for(int i = 0; i<size; i++) {
    			array[i] = nextLine();
    		}
    	}
    }
 
    public static class FastOutput extends PrintWriter {
    	public FastOutput() { 
            super(new BufferedOutputStream(System.out)); 
    	}
    	
    	public void printSideBySideSet(Set<Object> set, int size) {
    		boolean isFirstElementPrinted = false;
    		for(Object element : set) {
    			if(!isFirstElementPrinted) {
    				print(element);
    				isFirstElementPrinted = true;
    				
    				return;
    			}
    			print(" "+element);
    		}
    		println();
    	}
    	
    	public void printLineByLineSet(Set<Object> set, int size) {
    		for(Object element : set) {
    			println(element);
    		}
    	}
    	
    	public void printSideBySideList(ArrayList<Object> list, int size) {
    		print(list.get(0));
    		for(int i = 1; i<size; i++) {
    			print(" "+list.get(i));
    		}
    		println();
    	}
    	
    	public void printLineByLineList(ArrayList<Object> list, int size) {
    		for(int i = 0; i<size; i++) {
    			println(list.get(i));
    		}
    	}
    	
    	public void printSideBySideArray(Object [] array, int size) {
    		print(array[0]);
    		for(int i = 1; i<size; i++) {
    			print(" "+array[i]);
    		}
    		println();
    	}
    	
    	public void printLineByLineArray(Object [] array, int size) {
    		for(int i = 0; i<size; i++) {
    			println(array[i]);
    		}
    	}
    }
}