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 c_{i} 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 c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^7), here c_{i} 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 t_1, t_2, ..., t_{n} (k + 1 ≤ t_{i} ≤ k + n), here t_{i} 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())
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)


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)


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, 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)))


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)


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)