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.util.*;

public class main
{
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long mod = 1000000000 + 7;
	private static long mod1 = 1000000000 + 9;
	private static int MAX = 1000001;
	private static int block;
	// private static int[] dfs1;
	private static int[] tin;
	private static int[] tout;

	// private static Node[] nodes1;
	// private static ArrayList<Integer>[] list;
	private static void soln()
	{
		int n = nextInt();
		int k = nextInt();
		Pair[] arr = new Pair[n];
		TreeSet<Integer> set = new TreeSet<>();
		for (int i = 0; i < n; i++)
		{
			set.add(k + i);
			arr[i] = new Pair(i, nextInt());
		}
		Arrays.sort(arr);
		long cost = 0;
		int[] ans = new int[n];
		for (int i = 0; i < n; i++)
		{
			Pair tmp = arr[i];
			int x = set.ceiling(tmp.i);
			cost += ((long) (x - tmp.i)) * ((long) tmp.v);
			ans[tmp.i] = x;
			set.remove(x);
		}
		pw.println(cost);
		for (int i = 0; i < n; i++)
			pw.print((ans[i] + 1) + " ");
		pw.println();
	}

	public static class Pair implements Comparable<Pair>
	{
		int i, v;

		public Pair(int a, int b)
		{
			i = a;
			v = b;
		}

		public int compareTo(Pair a)
		{
			return a.v - v;
		}
	}

	public static class Merge
	{
		public void sort(int inputArr[])
		{
			int length = inputArr.length;
			doMergeSort(inputArr, 0, length - 1);
		}

		private void doMergeSort(int[] arr, int lowerIndex, int higherIndex)
		{
			if (lowerIndex < higherIndex)
			{
				int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
				doMergeSort(arr, lowerIndex, middle);
				doMergeSort(arr, middle + 1, higherIndex);
				mergeParts(arr, lowerIndex, middle, higherIndex);
			}
		}

		private void mergeParts(int[] array, int lowerIndex, int middle, int higherIndex)
		{
			int[] temp = new int[higherIndex - lowerIndex + 1];
			for (int i = lowerIndex; i <= higherIndex; i++)
			{
				temp[i - lowerIndex] = array[i];
			}
			int i = lowerIndex;
			int j = middle + 1;
			int k = lowerIndex;
			while (i <= middle && j <= higherIndex)
			{
				if (temp[i - lowerIndex] < temp[j - lowerIndex])
				{
					array[k] = temp[i - lowerIndex];
					i++;
				} else
				{
					array[k] = temp[j - lowerIndex];
					j++;
					// cnt+=(middle+1-i);
				}
				k++;
			}
			while (i <= middle)
			{
				array[k] = temp[i - lowerIndex];
				k++;
				i++;
			}
			while (j <= higherIndex)
			{
				array[k] = temp[j - lowerIndex];
				k++;
				j++;
			}
			/*
			 * pw.println(lowerIndex+" "+higherIndex); for(int
			 * m=lowerIndex;m<=higherIndex;m++) pw.print(array[m]+" "); pw.println();
			 */
		}
	}

	static void multiply(long[][] a, long[][] b, long m)
	{
		int n = a.length;
		long[][] mul = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				mul[i][j] = 0;
				for (int k = 0; k < n; k++)
					mul[i][j] = (mul[i][j] + (a[i][k] * b[k][j]) % m) % m;
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = mul[i][j];
	}

	private static long pow(long a, long b, long c)
	{
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}

	private static class Mo implements Comparable<Mo>
	{
		int l;
		int r;
		int i;

		public Mo(int a, int b, int ind)
		{
			l = a;
			r = b;
			i = ind;
		}

		@Override
		public int compareTo(Mo arg0)
		{
			int b1 = this.l / block;
			int b2 = arg0.l / block;
			return (b1 != b2) ? (b1 - b2) : (this.r - arg0.r);
		}
	}

	private static long gcd(long n, long l)
	{
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}

	private static long max(long a, long b)
	{
		if (a > b)
			return a;
		return b;
	}

	private static long min(long a, long b)
	{
		if (a < b)
			return a;
		return b;
	}

	public static void main(String[] args) throws Exception
	{
		new Thread(null, new Runnable()
		{
			@Override
			public void run()
			{
				/*
				 * try { InputReader(new FileInputStream(
				 * "C:\\Users\\hardik\\Desktop\\C-small-1-attempt1.in")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				/*
				 * try { pw=new PrintWriter(new
				 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				soln();
				pw.close();
			}
		}, "1", 1 << 26).start();
	}

	public static void InputReader(InputStream stream1)
	{
		stream = stream1;
	}

	private static boolean isWhitespace(int c)
	{
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c)
	{
		return c == '\n' || c == '\r' || c == -1;
	}

	private static 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++];
	}

	private static 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;
	}

	private static 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;
	}

	private static String nextToken()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static 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();
	}

	private static int[] nextIntArray(int n)
	{
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
		{
			arr[i] = nextInt();
		}
		return arr;
	}

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

	private static void pArray(int[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c)
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private static char nextChar()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(c))
			c = read();
		return c1;
	}

	private interface SpaceCharFilter
	{
		public boolean isSpaceChar(int ch);
	}
}