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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.Random;
import java.util.StringTokenizer;


public class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int N = in.nextInt();
        int K = in.nextInt();

        Item[] items = new Item[N+1];
        for(int i=1; i <= N; ++i) {
            Item item = new Item();
            item.cost = in.nextInt();
            item.idx = i;
            items[i] = item;
        }

        Sort<Item> sort = new QuickSort<Item>((Item a, Item b)-> {
            return b.cost - a.cost;
        });
        sort.sort(items, 1, N);

        FindSetImp fs = new FindSetImp(N*2+10);
        fs.init(K+1, N+K+1);

        int[] orders = new int[N+1];
        long ans = 0;

        for(int i=1; i <= N; ++i) {
            Item item = items[i];
            int pos = Compare.max(item.idx, K+1);
            int rt = fs.getRoot(pos);

            pos = fs.mx[rt];
            orders[item.idx] = pos;
            ans += (long) item.cost * (long) (pos-item.idx);

            fs.union(rt, pos+1);
        }

        StringBuilder out = new StringBuilder();
        out.append(ans).append('\n').append(orders[1]);
        for(int i=2; i <= N; ++i) out.append(' ').append(orders[i]);
        System.out.println(out);
    }
}

class Compare {
    public static int min(int a, int b) {
        return a < b? a: b;
    }

    public static int max(int a, int b) {
        return a > b? a: b;
    }

    public static long min(long a, long b) {
        return a < b? a: b;
    }

    public static long max(long a, long b) {
        return a > b? a: b;
    }

    public static double min(double a, double b) {
        return a < b? a: b;
    }

    public static double max(double a, double b) {
        return a > b? a: b;
    }

    public static <T extends Comparable> T min(T A, T B) {
        return A.compareTo(B) < 0? A: B;
    }

    public static <T extends Comparable> T max(T A, T B) {
        return A.compareTo(B) > 0? A: B;
    }
}
interface Sort<T> {
    void sort(T[] targets, int offset, int length);
    void setComparator(Comparator<T> comparator);
}
class QuickSort<T> implements Sort<T> {
    private Random random = new Random();
    private Comparator<T> comparator;

    public QuickSort() {}

    public QuickSort(Comparator<T> comparator) {
        setComparator(comparator);
    }


    @Override
    public void sort(T[] targets, int offset, int length) {
        int end = offset + length;
        assert length >= 1 && offset >= 0 && offset < targets.length && end <= targets.length
                : "Out of bound of array:\nlength: " + targets.length + ", end: " + end;
        if( length > 1 ) quickSort(targets, offset, end);
    }

    @Override
    public void setComparator(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    private void quickSort(T[] targets, int begin, int end) {
        int lft = begin, rht = end-1;
        int mid = lft + random.nextInt(end-begin);

        T target = targets[mid];
        while( lft <= rht ) {
            while( comparator.compare(targets[lft], target) < 0 ) ++lft;
            while( comparator.compare(targets[rht], target) > 0 ) --rht;
            if( lft <= rht ) {
                T tmp = targets[lft];
                targets[lft] = targets[rht];
                targets[rht] = tmp;
                ++lft; --rht;
            }
        }

        ++rht;
        if( begin+1 < rht ) quickSort(targets, begin, rht);
        if( lft+1 < end ) quickSort(targets, lft, end);
    }
}
interface FindSet {
    void init(int N);
    int getRoot(int x);
    void union(int x, int y);
}
class HeuristicFindSet implements FindSet {
    protected int N;
    public final int[] f;
    public final int[] cnt;
    public HeuristicFindSet(int size) {
        f = new int[size+1];
        cnt = new int[size+1];
    }

    @Override
    public void init(int N) {
        assert N < f.length: "Out of bound of array";
        this.N = N;
        for(int i=1; i <= N; ++i) f[i] = 0;
        for(int i=1; i <= N; ++i) cnt[i] = 1;
    }

    @Override
    public int getRoot(int x) {
        return f[x] > 0? f[x]=getRoot(f[x]): x;
    }

    @Override
    public void union(int x, int y) {
        int rx = getRoot(x);
        int ry = getRoot(y);
        if( rx == ry ) return;
        if( cnt[rx] < cnt[ry] ) {
            f[rx] = ry;
            cnt[ry] += cnt[rx];
        } else {
            f[ry] = rx;
            cnt[rx] += cnt[ry];
        }
    }
}

class Scanner {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public Scanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in), 32768);
        tokenizer = null;
    }

    public Scanner(InputStream in, int size) {
        reader = new BufferedReader(new InputStreamReader(in), size);
        tokenizer = null;
    }

    public boolean hasNext() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (Exception e) {
                return false;
            }
        }
        return true;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}


class FindSetImp extends HeuristicFindSet {
    public final int[] mx;

    public FindSetImp(int size) {
        super(size);
        mx = new int[size+1];
    }

    public void init(int lft, int rht) {
        for(int i=lft; i <= rht; ++i) {
            f[i] = 0;
            cnt[i] = 1;
            mx[i] = i;
        }
    }

    @Override
    public void union(int x, int y) {
        int rx = getRoot(x);
        int ry = getRoot(y);
        if( rx == ry ) return;
        if( cnt[rx] < cnt[ry] ) {
            f[rx] = ry;
            cnt[ry] += cnt[rx];
            mx[ry] = Compare.max(mx[rx], mx[ry]);
        } else {
            f[ry] = rx;
            cnt[rx] += cnt[ry];
            mx[rx] = Compare.max(mx[rx], mx[ry]);
        }
    }
}

class Item {
    public int cost, idx;
}