No tag edit access

A. Planning

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputHelen 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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2017 01:25:58 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|