Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are n flights that must depart today, the i-th of them is planned to depart at the i-th minute of the day.

Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first k minutes of the day, so now the new departure schedule must be created.

All n scheduled flights must now depart at different minutes between (k + 1)-th and (k + n)-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.

Helen knows that each minute of delay of the i-th flight costs airport ci burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 300 000), here n is the number of flights, and k is the number of minutes in the beginning of the day that the flights did not depart.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 107), here ci is the cost of delaying the i-th flight for one minute.

Output

The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain n different integers t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n), here ti is the minute when the i-th flight must depart. If there are several optimal schedules, print any of them.

Example

Input

5 2
4 2 1 10 2


Output

20
3 6 7 4 5 

Note

Let us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles. 

However, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 burles.
/*
 * DA-IICT
 * Author: Jugal Kalal
 */
import java.util.*;
import java.io.*;
import java.math.*;
public class Codeforces{
	static long mod=(long)Math.pow(10,9)+7l;
	public static void main(String args[]){
        new Thread(null, new Runnable() {
            public void run() {
                try{
                    solve();
                    w.close();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();
	}
	static InputReader in;
    static PrintWriter w;
    static void solve(){
        in = new InputReader(System.in);
        w = new PrintWriter(System.out);
        PriorityQueue<Pair> pq=new PriorityQueue<>(new Comp());
        int n=in.nextInt();
        long k=in.nextLong();
        long costs[]=new long[n+1];
        for(int i=1;i<=n;i++) {
        		costs[i]=in.nextLong();
        }
        for(int i=1;i<=k;i++) {
        		pq.add(new Pair((long)i,costs[i]));
        }
        long ans=0;
        long time=k+1;
        long fans[]=new long[n+1];
        while(!pq.isEmpty()) {
        		if(time<=n) {
        			pq.add(new Pair((long)time,costs[(int)time]));
        		}
        		Pair p=pq.poll();
        		fans[(int)p.time]=time;
        		ans+=Math.abs(p.time-time)*costs[(int)p.time];
        		time++;
        }
        w.println(ans);
        for(int i=1;i<=n;i++) {
        		w.print(fans[i]+" ");
        }
        w.println();
    }
    static class Comp implements Comparator<Pair>{
    		@Override
    		public int compare(Pair p1,Pair p2) {
    			if(p1.cost!=p2.cost) {
    				return (int)(p2.cost-p1.cost);
    			}
    			return (int)(p1.time-p2.time);
    		}
    }
    static class Pair{
    		long time;
    		long cost;
    		public Pair(long time,long cost) {
    			this.time=time;
    			this.cost=cost;
    		}
    }
    static ArrayList<Integer> adj[]; //Adjacency Lists
    static int V;   // No. of vertices
    // Constructor
    static void Graph(int v){
        V = v;
        adj = new ArrayList[v];
        for (int i=0; i<v; ++i){
        	adj[i] = new ArrayList();
        }
    }
    // Function to add an edge into the graph
    static void addEdge(int u,int v){
		adj[u].add(v);
		adj[v].add(u);
    }
    static HashSet<Integer> set=new HashSet<>();
    static void sieve(int N){
	   	 boolean isPrime[]=new boolean[N+1];
	   	 isPrime[0] = true;
	   	 isPrime[1] = true;
	   	 for(int i = 2; i * i <= N; ++i) {
	   	      if(isPrime[i] == false) {//Mark all the multiples of i as composite numbers
	   	          for(int j = i * i; j <= N ;j += i)
	   	              isPrime[j] = true;
	   	     }
	   	 }
	   	 for(int i=0;i<=N;i++) {
	   		 if(!isPrime[i]) {
	   			 set.add(i);
	   		 }
	   	 }
   	}
    static int Arr[];
    static long size[];
  //modified initialize function:
    static void initialize(int N){
    		Arr=new int[N];
    		size=new long[N];
        for(int i = 0;i<N;i++){
        	Arr[ i ] = i ;
        	size[ i ] = 1;
        }
    }
    static boolean find(int A,int B){
        if( root(A)==root(B) )//if A and B have same root,means they are connected.
        return true;
        else
        return false;
    }
 // modified root function.
    static void weighted_union(int A,int B){
        int root_A = root(A);
        int root_B = root(B);
        if(size[root_A] < size[root_B ]){
        	Arr[ root_A ] = Arr[root_B];
        	size[root_B] += size[root_A];
        }
        else{
        	Arr[ root_B ] = Arr[root_A];
        	size[root_A] += size[root_B];
        }
    }
    static int root (int i){
        while(Arr[ i ] != i){
            Arr[ i ] = Arr[ Arr[ i ] ] ; 
            i = Arr[ i ]; 
        }
        return i;
    }
//    static long[] isHamiltonian_path(int n){
//    	boolean dp[][]=new boolean[n][1<<n];
//    	long ans[]=new long[n];
//    	long sum[]=new long[n];
//    	for(int i=0;i<n;i++){
//    		dp[i][1<<i]=true;
//    		ans[i]=0;
//    		sum[i]=i+1;
//    	}
//    	for(int mask=0;mask<(1<<n);mask++){
//    		int s=0;
//    		int count=0,temp=mask;
//    		while(temp>0){
//    			s+=1+Math.log(temp&(-temp))/Math.log(2);
//    			temp=temp&(temp-1);
//    			count++;
//    		}
//    		for(int j=0;j<n;j++){
//    			if((mask&(1<<j))>0){
//    				for(int k=0;k<n;k++){
//    					if(j!=k&&(mask&(1<<k))>0&&adj[j][k]&&dp[k][mask^(1<<j)]){
//    						dp[j][mask]=true;
//    						ans[j]=Math.max(ans[j],count-1);
//    						if(ans[j]==count-1){
//    							sum[j]=Math.max(sum[j], s);
//    						}
//    					}
//    				}
//    			}
//    		}
//    	}
//    	return sum;
//    }
    static long gcd(long a,long b){
		if(a==0){
			return b;
		}
		return gcd(b%a,a);
	}
    static long power(long base, long exponent, long modulus){
	    long result = 1L;
	    while (exponent > 0) {
	        if (exponent % 2L == 1L)
	            result = (result * base) % modulus;
	        exponent = exponent >> 1;
	        base = (base * base) % modulus;
	    }
	    return result;
	}
    static HashMap<Long,Long> primeFactors(long n){
        HashMap<Long,Long> ans=new HashMap<Long,Long>();
    	// Print the number of 2s that divide n
        while (n%2L==0L)
        {
            if(ans.containsKey(2L)){
            	ans.put(2L,ans.get(2L)+1L);
            }else{
            	ans.put(2L,1L);
            }
            n /= 2L;
        }
 
        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (long i = 3; i <= Math.sqrt(n); i+= 2L)
        {
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
            	if(ans.containsKey(i)){
                	ans.put(i,ans.get(i)+1L);
                }else{
                	ans.put(i,1L);
                }
                n /= i;
            }
        }
 
        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            ans.put(n,1L);
        return ans;
    }
////for marking all prime numbers greater than 1 and less than equal to N
	
//  //if  str2 (pattern) is subsequence of str1 (Text) or not
//	static boolean function(String str1,String str2){
//	     str2 = str2.replace("", ".*");  //returns .*a.*n.*n.*a.
//	     return (str1.matches(str2));  // returns true
//	}
    
    
 
	static boolean isPrime(long n){
		if(n < 2L) return false;
		if(n == 2L || n == 3L) return true;
		if(n%2L == 0 || n%3L == 0) return false;	
		long sqrtN = (long)Math.sqrt(n)+1L;
		for(long i = 6L; i <= sqrtN; i += 6L) {
			if(n%(i-1) == 0 || n%(i+1) == 0) return false;
		}
		return true;
	}
//	static HashMap<Integer,Integer> level;;
//	static HashMap<Integer,Integer> parent;
//	static boolean T[][][];
//	static void subsetSum(int input[], int total, int count) {
//        T = new boolean[input.length + 1][total + 1][count+1];
//        for (int i = 0; i <= input.length; i++) {
//        	T[i][0][0] = true;
//        	for(int j = 1; j<=count; j++){
//        		T[i][0][j] = false;
//        	}
//        }
//        int sum[]=new int[input.length+1];
//        for(int i=1;i<=input.length;i++){
//            sum[i]=sum[i-1]+input[i-1];
//        }
//        for (int i = 1; i <= input.length; i++) {
//            for (int j = 1; j <= (int)Math.min(total,sum[i]); j++) {
//            	for (int k = 1; k <= (int)Math.min(i,count); k++){
//            		 if (j >= input[i - 1]) {//Exclude and Include
//                         T[i][j][k] = T[i - 1][j][k] || T[i - 1][j - input[i - 1]][k-1];
//                     } else {
//                         T[i][j][k] = T[i-1][j][k];
//                     }
//            	}
//            }
//        }
//    }
//	static <K,V extends Comparable<? super V>>
//	SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map){
//	    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
//	        new Comparator<Map.Entry<K,V>>() {
//	            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
//	                int res = e2.getValue().compareTo(e1.getValue());
//	                return res != 0 ? res : 1;
//	            }
//	        }
//	    );
//	    sortedEntries.addAll(map.entrySet());
//	    return sortedEntries;
//	}
	
 
	 
	//minimum prime factor of all the numbers less than n
    static int minPrime[];
	static void minimumPrime(int n){
		minPrime=new int[n+1];
		minPrime[1]=1;
        for (int i = 2; i * i <= n; ++i) {
            if (minPrime[i] == 0) {         //If i is prime
                for (int j = i * i; j <= n; j += i) {
                    if (minPrime[j] == 0) {
                        minPrime[j] = i;
                    }
                }
            }
        }
        for (int i = 2; i <= n; ++i) {
            if (minPrime[i] == 0) {
                minPrime[i] = i;
            }
        }
	}
	static long modInverse(long A, long M){
		long x=extendedEuclid(A,M)[0];
		return (x%M+M)%M;    //x may be negative
	}
	static long[] extendedEuclid(long A, long B){
		if(B == 0) {
			long d = A;
			long x = 1;
			long y = 0;
			return new long[]{x,y,d};
		}
		else {
			long arr[]=extendedEuclid(B, A%B);
			long temp = arr[0];
			arr[0] = arr[1];
			arr[1] = temp - (A/B)*arr[1];
			return arr;
		}
	}
 
	static class InputReader{
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, numChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream){
            this.stream = stream;
        }
        
        public int read(){
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
 
        public String nextLine(){
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public String readString(){
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public long nextLong(){
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int nextInt(){
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n){
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
 
        public long[] nextLongArray(int n){
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
 
        public boolean isSpaceChar(int c){
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c){
            return c == '\n' || c == '\r' || c == -1;
        }
        public interface SpaceCharFilter{
            public boolean isSpaceChar(int ch);
        }
	}
}  