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.
	import java.io.*;



import java.math.*;
import java.nio.file.attribute.AclEntry.Builder;
import java.security.KeyStore.Entry;
import java.util.*;


	 
	public  class Khatri {
		private InputStream is;
		private PrintWriter out;
		int time = 0, dp[][], DP[], start[], end[], dist[],  black[];
		static int MOD = (int)(1e9+7);
		int arr[];
		int weight[][];
		int x[];
		int y[];
		int parent[];
		int MAX = 800000, N, K, L;
		long red[];
		ArrayList<Integer>[] amp;
		//boolean b[], boo[][];
		Pair prr[];
		HashSet<Integer> hs = new HashSet<>();
		long Dp[][][][] = new long[110][110][12][12];
	 
		public static void main(String[] args) throws Exception 
		{
			new Thread(null, new Runnable() 
			{
			public void run() 
			{
				try {
	 
			//new CODEFORCES().soln();
			} catch (Exception e) 
				{
					System.out.println(e);
				}
			}
		}, "1", 1 << 26).start();
			new Khatri().soln();
		}
		char ch[][];
		//int ans = 0, cnt = 0, Q;
		int n1, n2, k1, k2, M;
		static ArrayList<Integer>[] g;
        static ArrayList<Integer> ar[];
		static long ok[];	
		static int a[];
		static int phi[]=new int[500005];
        void solve()
        {
        int n=ni();
        int k=ni();
        Pair p[]=new Pair[n];
        for(int i=0;i<n;i++)
        {
        	p[i]=new Pair(ni(),i+1);
        }
        Arrays.sort(p);
        TreeSet<Integer> set=new TreeSet();
        for(int i=k+1;i<=(k+n);i++)
        {
        	set.add(i);
        }
        int ans[]=new int[n+1];
        long cost=0;
        long fina=0;
        for(int i=0;i<n;i++)
        {
        	int index=p[i].ind;
        	if(set.contains(index))
        	{
        		ans[index]=index;
        		set.remove(index);
        		continue;
        	}
        	int tmp=set.higher(index);
        	ans[index]=tmp;
        	set.remove(tmp);
        	cost=((long)tmp-(long)index);
        	cost*=(long)p[i].val;
        	fina+=cost;
        }
        out.println(fina);
        for(int i=1;i<=n;i++)
        {
        	out.print(ans[i]+" ");
        }
        }
        
       
		public static void Update(int v,int tl,int tr,int l2,long tot)
    	{
    		if(tl==tr)
    		{
    			tre[v]+=tot;
    			if(tre[v]<0)
    				tre[v]+=MOD;
    			else
    			tre[v]%=MOD;
    		}
    		else
    		{
    			int mid=(tl+tr)/2;
    			if(tl <= l2 &&l2 <= mid)
    	        {
    	            Update(2*v,tl, mid, l2, tot);
    	        }
    	        else
    	        {
    	        	Update(2*v+1,mid+1,tr, l2, tot);
    	        }
    			tre[v]=(tre[2*v]+tre[2*v+1])%MOD;
    		}
    	}
        static long tre[]=new long[4000006];
        public static long find(int v,int start,int end,int l,int r)
    	{
    	    if(r < start || end < l)
    	    {
    	    	return 0;
    	    }
    	    if(l <= start && end <= r)
    	    {
    	        return (tre[v]);
    	    }
    	    int mid = (start + end) / 2;
    	    long p1 = find(2*v, start, mid, l, r);
    	    long p2 = find(2*v+1, mid+1, end, l, r);
    	    return (p1+p2)%MOD;         
    	}
        private static void Process(List<String> list){
    	    Collections.sort(list,(x,y)->-((x+y).compareTo(y+x)));
    	    String p=String.join("",list);
    	    int c=0;
    	    for(int i=0;i<p.length();i++)
    	    	if(p.charAt(i)=='0')
    	    		c++;
    	    if(c==p.length())
    	    	System.out.println("0");
    	    else
    	    System.out.println(String.join("",list));
    	}
        
        boolean check(long num, long s) {
    		long sum = 0;
    		long nm = num;
    		while (nm != 0) {
    			sum += nm % 10;
    			nm /= 10;
    		}
    		if (num - sum >= s)
    			return true;
    		return false;
    	}

        private void dfsCF(int i) {
			visited[i]=true;
			count++;
			edjes+=(g[i].size());
			for(int x:g[i])
			{
				if(!visited[x])
				{
					dfsCF(x);
				}
			}
		}
		static int count=0;
		static int edjes=0;
        static int hight[]=new int[200004];
        static int frq[]=new int[200005];
        static long ans[]=new long[200005];
        public static void dfsGcd(int curr,int h,long o)
        {
        	hight[curr]=h;
        	visited[curr]=true;
        	for(int x:g[curr])
        	{
        		if(!visited[x])
        		{
        			ans[x]=gcd(o,a[curr]);
        			dfsGcd(x,h+1,gcd(o,a[curr]));
        		}
        	}
        }
        public static void GCD(int curr)
        {
        	for(int x:ar[a[curr]])
        	{
        		if(frq[x]==(hight[curr]-1))
        		{
        			ans[curr]=Math.max(ans[curr],x);
        		}
        	}
        	for(int x:ar[a[curr]])
        		frq[x]++;
        	visited[curr]=true;
        	for(int x:g[curr])
        	{
        		if(!visited[x])
        		{
        			GCD(x);
        		}
        	}
        	for(int x:ar[a[curr]])
        		frq[x]--;
        }
		static boolean visited[]=new boolean[1000005];

            boolean isPrime(int x)
            {
            if(x==0||x==1)
            	return false;
			for(int i = 2;i*1L*i<=x;i++) if(x%i==0) return false;
			return true;
		}
	    int  p ;
		void buildGraph(int n)
		{
			for(int i = 0; i<n ;i++){
				int x1 = ni() -1, y1 = ni()-1;
				amp[x1].add(y1);
				amp[y1].add(x1);
				x[i] = x1; y[i] = y1;
			}
		}
		long get(int x){
			long val = 0;
			for(int i = 0; i< N; i++){
				val += Math.abs(x-arr[i]);
				x+=L;
			}
			return val;
		}
		
		long modInverse(long a, long mOD2){
	        return  power(a, mOD2-2, mOD2);
		}
		long power(long x, long y, long m)
		{
			if (y == 0)
	    return 1;
		long p = power(x, y/2, m) % m;
		p = (p * p) % m;
	 
		return (y%2 == 0)? p : (x * p) % m;
		}
		
		public static long gcd(long a, long b){
			if(b==0) return a;
			return gcd(b,a%b);
		}
		
		public static int[] shuffle(int[] a, Random gen){
			for(int i = 0, n = a.length;i < n;i++)
			{ 
				int ind = gen.nextInt(n-i)+i; 
				int d = a[i]; 
				a[i] = a[ind];
				a[ind] = d; 
			} 
		return a; 
		}
	 
		class Pair implements Comparable<Pair>{
			int val,ind;
			Pair(int ind,int off_sal){
				this.val = ind;
				this.ind = off_sal;
			}
			
			public int hashCode() {
				return Objects.hash();
			}
			
			public int compareTo(Pair other) {
			return (int)(other.val-this.val);
			}
			
		}
		class Pair1 implements Comparable<Pair1>{
			long index;
			long val;
			Pair1(long s,long time){
			this.index=s;
			this.val=time;
			//this.min=Integer.MAX_VALUE;
			}
			public int hashCode() {
				return Objects.hash();
			}
			
			@Override
			public int compareTo(Pair1 arg0) {
				return (int)(val-arg0.val);
			}
			
		}
		long power(long x, long y, int mod){
			long ans = 1;
			while(y>0){
				if(y%2==0){
					x = (x*x)%mod;
					y/=2;
				}
				else{
					ans = (x*ans)%mod;
					y--;
				}
			}
			return ans;
		}
		void soln() {
			is = System.in;
			out = new PrintWriter(System.out);
			long s = System.currentTimeMillis();
			solve();
			//out.close();
			out.flush();
			//tr(System.currentTimeMillis() - s + "ms");
		}
	 
	 
		// To Get Input
		// Some Buffer Methods
		private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
										// ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	 
		private void tr(Object... o) {
			if (!oj)
				System.out.println(Arrays.deepToString(o));
		}
	} 