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.util.*;
import java.io.*;
 
 
   
 
 
 
   public  class Sample implements Runnable{
   // static ArrayList<Integer>[] al;
         static class Pair implements Comparable<Pair>{
  long a;
  int b;
 
   
  Pair(){
 
  }
  Pair(long a,int b){
      this.a=a;
      this.b=b;
      

  }
   
  public int compareTo(Pair x)
        {

   
        return Long.compare(x.a,this.a);
    }
}
  static class Beauty implements Comparator<Beauty>{
    int beauty;
    int cost;
    Beauty(){
        }
    Beauty(int beauty,int cost){
      this.beauty=beauty;
      this.cost=cost;
 
    }
    public int compare(Beauty b1,Beauty b2 ){
      if(b2.beauty-b1.beauty==0){
        return b1.cost-b2.cost;
      }else{
        return b2.beauty-b1.beauty;
      }
    }
 
  }
   
  

   static InputReader sc = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out); 
   static int gcd(int a,int b){
    if(a==0){
      return b;
    }
    return gcd(b%a,a);
   }
   static int d;
   static int[] color;
   static boolean[] v;
  /*  static void dfs(int src,int x,int y){
      v[src]=true;
     int  i=1;
     color[src]=x;
      for(int a :al[src]){
        if(v[a]) continue;
        if(i==x|| i==y){
          i++;
          if(i==x|| i==y){
          i++;
        }
        }
        color[a]=i;
        i++;
         
      }
      for(int a:al[src]){
        if(!v[a]){
          dfs(a,color[a],x);
        }
      }
 
 
 
    }*/
    static long[] a;
    static long[] b;
    public static boolean possible(double mid,int n){
      double l=a[1]-b[1]*mid;
      double r=a[1]+b[1]*mid;
      for(int i=2;i<=n;i++){
        l=Math.max(l,a[i]-b[i]*mid);
        r=Math.min(r,a[i]+b[i]*mid);
 
      }
      if(l>r)return false;
      else  return true;
    }
 
public static boolean isvowel(char ch){
    if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'){
        return true;
    }else{
        return false;
    }
}
static long[] fac;
 static long[] inv;
 static long mod=(long)1e9+7;
static int[] prime;
static Integer[] ans;
 
static ArrayList<Integer>[] al1;
static ArrayList<Integer>[] al2;
static int[] lol1;
static int[] lol2;
static boolean[] v1;
static boolean[] v2;
 
 
    
     public static void main(String[] args) throws IOException
    { 
         new Thread(null, new Sample(), "whatever", 1<<26).start();
         

      
    }
   

   

     boolean findSum(int set[], int n, long sum)
    {
       // Base Cases
       if (sum == 0)
         return true;
       if (n == 0 && sum != 0)
         return false;
      
       // If last element is greater than sum, then ignore it
       if (set[n-1] > sum)
         return findSum(set, n-1, sum);
      
       /* else, check if sum can be obtained by any of the following
          (a) including the last element
          (b) excluding the last element   */
       return findSum(set, n-1, sum) || 
                                   findSum(set, n-1, sum-set[n-1]);
    }
 
 
  public class IntegerComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
    static int[] pro_a;
    static ArrayList pro_b[];
    static ArrayList<Integer> seg[];
    public static void build(int low,int high,int pos){
      if(low>high){ return ;}
      if(low==high){
        seg[pos]=pro_b[low];
        return;
        
      }
      int mid=(low+high)>>1;
      build(low,mid,2*pos+1);
      build(mid+1,high,2*pos+2);
      seg[pos]=merge(seg[2*pos+1],seg[2*pos+2]);
      
    }
    public static ArrayList merge(ArrayList<Integer> a1,ArrayList<Integer> a2){
      ArrayList<Integer> result=new ArrayList<Integer>();
      int i=0;
      int j=0;
      while(i<a1.size() && j<a2.size()){
        if((a1.get(i))<(a2.get(j))){
         
          result.add(a1.get(i));
           i++;
        }
        else if(a1.get(i)>a2.get(j)){
          
          result.add(a2.get(j));
          j++;
        }
        else{
         
          result.add(a1.get(i));
          result.add(a2.get(j));
           i++;j++;
        }

      }
      while(i<a1.size()){
        result.add(a1.get(i));
        i++;
      }
      while(j<a2.size()){
        result.add(a2.get(j));
          j++;
      }
       
      
      return result;
    }
    public int find(int low,int high,int pos,int l,int r,int x,int y){
          if(l<=low && high<=r){
            int find_x=lower_bound(seg[pos],x);
            int find_y=upper_bound(seg[pos],y);
          // System.out.println(find_x+" "+find_y);
            return (find_y-find_x);
          }
          if(l>high || r<low){
            return 0;
          }
          int mid=(low+high)>>1;
          return find(low,mid,2*pos+1,l,r,x,y)+find(mid+1,high,2*pos+2,l,r,x,y);
    }
    int lower_bound(ArrayList<Integer> a, int key) {
        int l = 0;
        int h = a.size(); // Not n - 1
 
        
        
        while (l < h) {
            int mid = (l + h) / 2;
            if (key <= a.get(mid)) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
      int upper_bound(ArrayList<Integer> a, int key) {
        int l = 0;
          int h = a.size(); // Not n - 1
 
          if(key>=a.get(h-1))
          return (h);
        
        while (l < h) {
            int mid = (l + h) / 2;
            if (key >= a.get(mid)) {
                l = mid + 1;
            } else {
                h = mid;
            }
        }
  
        return l;
    }
    
    public void run(){
                 int n,k;
                 n=i();
                 k=i();
                 int[] cost=new int[n];
                 for(int i=0;i<n;i++)
                 {
                    cost[i]=i();

                 }
                   
                PriorityQueue<Pair> pq=new PriorityQueue();
                
                long count=0;
                Pair p;
                for(int i=0;i<n||!pq.isEmpty();i++)
                {
                  if(i<n)
                  {
                    pq.add(new Pair(cost[i],i));
                  }
                   
                  if(i>=k){
                    p=(Pair)pq.remove();
                    cost[p.b]=i+1;
                    count+=1L*(i-p.b)*p.a;
                  }
                  
                   
                }

                out.println(count);
                for(int i=0;i<n;i++){
                out.print(cost[i]+" ");
                }

                 out.close();
       }
                
                
                  



       
       

       
       
       
     public static int lower_bound_array(int[] arr, long key) {
    int len = arr.length;
    int lo = 0;
    int hi = len-1;
    int mid = (lo + hi)/2;
    while (true) {
      int cmp = Long.compare(arr[mid],(key));
       
        if (cmp < 0) {
        lo = mid+1;
        if (hi < lo)
          return mid<len-1?mid+1:-1;
      } else {
        hi = mid-1;
        if (hi < lo)
          return mid;
      }
      mid = (lo + hi)/2;
    }
  }
         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    
    /////////////////////////////////////////////////////////// shortcuts //////////////////////////////
      public static long modPow(long base, long exp, long mod) {
        base = base % mod;
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
                exp--;
            } else {
                base = (base * base) % mod;
                exp = exp >> 1;
            }
 
        }
        return result;
    }
 
 
    public static void cal() {
        fac = new long[1000005];
        inv = new long[1000005];
        fac[0] = 1;
        inv[0] = 1;
        for (int i = 1; i <= 1000000; i++) {
            fac[i] = (fac[i - 1] * i) % mod;
            inv[i] = (inv[i - 1] * modPow(i, mod - 2, mod)) % mod;
        }
    }
 
   /* public static long ncr(int n, int r) {
        return (((fac[n] * inv[r]) % mod) * inv[n - r]) % mod;
    }
 */
 
      static int i() {
           
          return sc.nextInt();
        }
        static long l(){
          return sc.nextLong();
 
        }
       
         
        static String sL() throws IOException{
          return sc.nextLine();
        }
       static void loop(int[] a) throws IOException{
          for(int j=0;j<a.length;j++){
              a[j]=i();
          }
        }
        static void eloop(int[] a) throws IOException{
          for(int i=1;i<=a.length;i++){
              a[i]=i();
          }
        }
        static void ploop(int[] a)throws IOException{
             for(int j=0;j<a.length;j++){
                System.out.println(a[j]);
             }
 
        }
        static void eploop(int[] a)throws IOException{
             for(int j=1;j<=a.length;j++){
                System.out.println(a[j]);
             }
 
        } 
  
        ////////////////////////////////////////////////////////////////////////////////////////////////////
     
 
  static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
                this.stream = stream;
        }

        public int snext() {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars) {
                        curChar = 0;
                        try {
                                snumChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n) {
                long a[] = new long[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextLong();
                }
                return a;
        }

        
        public String nextLine() {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        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);
        }

    }
 
 }  
