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: competition

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=list(map(int,input().split()))
*l,=list(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 = 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)


# https://codeforces.com/problemset/problem/853/A
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)