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.

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.