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.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from heapq import heappush, heappop, heapify
(n, k) = map(int, input().split())
(*l,) = map(int, input().split())
q = [(-l[i], i) for i in range(k)]
heapify(q)
a = [0] * n
s = 0
for i in range(k, n):
	heappush(q, (-l[i], i))
	(x, j) = heappop(q)
	s -= x * (i - j)
	a[j] = i + 1
for i in range(n, n + k):
	(x, j) = heappop(q)
	s -= x * (i - j)
	a[j] = i + 1
print(s)
print(' '.join(map(str, a)))


from heapq import heappush, heappop, heapify
(n, k) = map(int, input().split())
c = list(map(int, input().split()))
q = [(-c[i], i) for i in range(k)]
heapify(q)
ans = 0
lis = [0] * n
for i in range(k, n):
	heappush(q, (-c[i], i))
	(a, p) = heappop(q)
	ans += a * (i - p)
	lis[p] = i + 1
for i in range(n, n + k):
	(a, p) = heappop(q)
	ans += a * (i - p)
	lis[p] = i + 1
print(-ans)
print(*lis)


import heapq
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
ans = [0] * n
h = []
for i in range(k):
	h.append((-1 * l[i], i))
heapq.heapify(h)
som = 0
for i in range(k, n + k):
	if i < n:
		heapq.heappush(h, (-1 * l[i], i))
	x = heapq.heappop(h)
	s = -1 * x[0] * (i - x[1])
	som += s
	ans[x[1]] = i + 1
print(som)
print(*ans)


from heapq import heappush, heappop
(n, k) = list(map(int, input().rstrip().split()))
c = list(map(int, input().rstrip().split()))
li = [0] * n
cost = 0
q = []
for i in range(k):
	heappush(q, (-c[i], i))
for i in range(k, n):
	heappush(q, (-c[i], i))
	(v, j) = heappop(q)
	li[j] = i + 1
	cost += -v * (i - j)
for i in range(k):
	(v, j) = heappop(q)
	li[j] = n + i + 1
	cost += -v * (n + i - j)
print(cost)
print(*li)


from heapq import heappush, heappop, heapify
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
q = [(-a[i], i) for i in range(k)]
heapify(q)
(res, s) = ([0] * n, 0)
for i in range(k, n):
	heappush(q, (-a[i], i))
	(x, j) = heappop(q)
	s -= x * (i - j)
	res[j] = i + 1
for i in range(n, n + k):
	(x, j) = heappop(q)
	s -= x * (i - j)
	res[j] = i + 1
print(s)
print(*res)


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heappush, heappop, heapify
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
q = [(-a[i], i) for i in range(k)]
heapify(q)
(res, s) = ([0] * n, 0)
for i in range(k, n):
	heappush(q, (-a[i], i))
	(x, j) = heappop(q)
	s -= x * (i - j)
	res[j] = i + 1
for i in range(n, n + k):
	(x, j) = heappop(q)
	s -= x * (i - j)
	res[j] = i + 1
print(s)
print(*res)


import sys
input = sys.stdin.readline
from heapq import *
(n, k) = map(int, input().split())
c = list(map(int, input().split()))
ic = [(-c[i], i + 1) for i in range(n)]
pq = []
idx = 0
ans_v = 0
ans_arr = [-1] * n
for t in range(k + 1, k + n + 1):
	while idx < n:
		if ic[idx][1] <= t:
			heappush(pq, ic[idx])
			idx += 1
		else:
			break
	(ci, i) = heappop(pq)
	ci *= -1
	ans_v += (t - i) * ci
	ans_arr[i - 1] = t
print(ans_v)
print(*ans_arr)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def safe(x, y):
	global n, m
	return 0 <= x < n and 0 <= y < m

def solve(case):
	(n, k) = sep()
	a = lis()
	if k >= n:
		h = []
		ans = 0
		order = [0] * n
		for i in range(n):
			ans += (k - i) * a[i]
		h = []
		for i in range(n):
			heappush(h, (-a[i], i))
		temp = heappop(h)
		order[temp[1]] = k
		for i in range(n - 1):
			(temp, j) = heappop(h)
			temp *= -1
			ans += (i + 1) * temp
			order[j] = k + i + 1
		print(ans)
		print(' '.join((str(order[i] + 1) for i in range(len(order)))))
	else:
		ans = 0
		for i in range(k + 1):
			ans += (k - i) * a[i]
		h = []
		sum = 0
		for i in range(k + 1):
			heappush(h, (-a[i], i))
			sum += a[i]
		order = [0] * n
		for i in range(k, k + n):
			(temp, j) = heappop(h)
			sum += temp
			ans += sum
			order[j] = i
			if i + 1 < n:
				heappush(h, (-a[i + 1], i + 1))
				sum += a[i + 1]
		print(ans)
		print(' '.join((str(order[i] + 1) for i in range(len(order)))))
(n, m) = (0, 0)
testcase(1)