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.
from heapq import heappush, heappop, heapify
n, k = list(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, heapify
n, k = list(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)
