A11262 | Planning

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.

The first line contains two integers $n$ and $k$ ( $1<=k<=n<=300000$ ), 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.

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.