Planning
Contest: Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 1500
Tags: greedy

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 ci burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

Input format:
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 c1, c2, ..., cn (1 ≤ ci ≤ 107), here ci is the cost of delaying the i-th flight for one minute.

Output format:
The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain n different integers t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n), here ti is the minute when the i-th flight must depart. If there are several optimal schedules, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

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.

Example input:
5 2
4 2 1 10 2

Example output:
20
3 6 7 4 5

Editorial:
We will show that following greedy is correct: let's for each moment of time use a plane, which can depart in this moment of time (and didn't depart earlier, of course) with minimal cost of delay.
Proof is quite simple: it's required to minimize $$\sum_{i=1}^{n} c_i \cdot (t_i - i) = \sum_{i=1}^{n} c_i \cdot t_i - \sum_{i=1}^{n} c_i \cdot i$$. You can notice that $$\sum_{i=1}^{n} c_i \cdot \vec{v}_i$$ is constant, so we just need to minimize $$\sum_{i=1}^{n} c_i \cdot t_i$$. Consider the optimal solution when plane i departs at moment bi and solution by greedy algorithm in which plane i departs at moment ai. Let x be plane with minimal cx, such ax ≠ bx. At any moment greedy algorithm takes avaliable plane with lowest cx, so ax < bx. Let y be a plane, such that by = ax. But cy >  = by, so bx·cx + by·cy >  = bx·cy + by·cx and it's possible to swap bx and by in optimal solution without loosing of optimality. By performing this operation many times it's possible to make bi = ai for each i and it means that greedy solution is optimal.
To make this solution work fast you need to use some data structures to find optimal plane faster for each moment. This data structure should be able to add number into set, give value of minimal element in set and erase minimal number from set. For this purpose you can use heap (or someting like std::set or std::priority_queue in C++).