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_ ≤ 107), 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.
[samples]
## 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.
Helen 在 Metropolis 机场工作，负责制定航班离港时间表。今天共有 #cf_span[n] 个航班必须起飞，第 #cf_span[i] 个航班原计划在当天第 #cf_span[i] 分钟起飞。
由于 Metropolis 机场是 Metropolia 的主要交通枢纽，维持时刻表十分困难。今天正是如此：由于技术问题，当天前 #cf_span[k] 分钟内没有航班起飞，因此必须重新制定离港时间表。
现在，所有 #cf_span[n] 个航班必须在第 #cf_span[(k + 1)] 分钟到第 #cf_span[(k + n)] 分钟（含）之间，选择不同的分钟起飞。然而，航班的起飞顺序可以与原计划不同——新时间表中的顺序可以调整。唯一的限制是：任何航班不得早于其原计划的起飞时间起飞。
Helen 知道，第 #cf_span[i] 个航班每延误一分钟，机场将损失 #cf_span[ci] 布尔。请帮助她确定新时间表中的航班起飞顺序，使得机场的总延误成本最小。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 300 000]），其中 #cf_span[n] 是航班数量，#cf_span[k] 是当天开始时航班未能起飞的分钟数。
第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 107]），其中 #cf_span[ci] 表示第 #cf_span[i] 个航班每延误一分钟的成本。
第一行必须输出航班延误的最小可能总成本。
第二行必须输出 #cf_span[n] 个互不相同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 个航班的起飞分钟。如果有多个最优方案，输出任意一个即可。
考虑样例测试：如果 Helen 将所有航班整体推迟 2 分钟并保持原有顺序，则总延误成本为 #cf_span[(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38] 布尔。
然而，样例答案中展示的更好方案的成本为 #cf_span[(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20] 布尔。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 300 000]），其中 #cf_span[n] 是航班数量，#cf_span[k] 是当天开始时航班未能起飞的分钟数。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 107]），其中 #cf_span[ci] 表示第 #cf_span[i] 个航班每延误一分钟的成本。
## Output
第一行必须输出航班延误的最小可能总成本。第二行必须输出 #cf_span[n] 个互不相同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 个航班的起飞分钟。如果有多个最优方案，输出任意一个即可。
[samples]
## Note
考虑样例测试：如果 Helen 将所有航班整体推迟 2 分钟并保持原有顺序，则总延误成本为 #cf_span[(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38] 布尔。然而，样例答案中展示的更好方案的成本为 #cf_span[(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20] 布尔。
**Definitions:**
- Let $ n $ be the number of flights.
- Let $ k $ be the number of initial minutes during which no flights could depart.
- Let $ c_i $ be the cost per minute of delay for flight $ i $, for $ i = 1, 2, \dots, n $.
- The original departure time of flight $ i $ is $ i $ (i.e., flight $ i $ was scheduled to depart at minute $ i $).
- The new departure times must be distinct integers in the range $ [k+1, k+n] $.
- Flight $ i $ cannot depart earlier than its original scheduled time $ i $: $ t_i \geq i $.
- The delay of flight $ i $ is $ t_i - i $, and its cost is $ c_i \cdot (t_i - i) $.
**Constraints:**
- $ t_i \in \{k+1, k+2, \dots, k+n\} $, all $ t_i $ distinct.
- $ t_i \geq i $ for all $ i \in \{1, 2, \dots, n\} $.
**Objective:**
Minimize total cost:
$$
\sum_{i=1}^{n} c_i \cdot (t_i - i)
$$
Equivalently, minimize:
$$
\sum_{i=1}^{n} c_i \cdot t_i - \sum_{i=1}^{n} c_i \cdot i
$$
Since $ \sum_{i=1}^{n} c_i \cdot i $ is constant, minimizing $ \sum_{i=1}^{n} c_i \cdot t_i $ is equivalent.
Thus, the problem reduces to:
**Assign distinct times $ t_i \in [k+1, k+n] $ to flights $ i $, subject to $ t_i \geq i $, to minimize $ \sum_{i=1}^{n} c_i t_i $.**
---
**Optimal Strategy (Greedy):**
To minimize $ \sum c_i t_i $, assign the **smallest available time slots** to the flights with the **largest $ c_i $** (since higher cost per minute should be penalized less by assigning earlier times).
However, each flight $ i $ has a **minimum allowed departure time** $ \max(i, k+1) $.
Thus, we can use a **greedy algorithm with a priority queue**:
1. Consider time slots from $ k+1 $ to $ k+n $ in order.
2. For each time slot $ t $, consider all flights $ i $ such that $ i \leq t $ (i.e., flights eligible to depart at or before $ t $).
3. Among all eligible flights not yet assigned, pick the one with the **maximum $ c_i $** and assign it to time $ t $.
4. Use a max-heap (priority queue) to efficiently select the flight with highest cost among those eligible at each step.
---
**Formal Algorithm:**
Let $ \text{heap} $ be a max-heap (priority queue) of pairs $ (c_i, i) $, keyed by $ c_i $.
Initialize:
- $ \text{heap} = \emptyset $
- $ j = 1 $ (index of next flight to consider for eligibility)
- $ \text{result}[1..n] $: array to store assigned departure times
For $ t = k+1 $ to $ k+n $:
1. While $ j \leq n $ and $ j \leq t $:
Push $ (c_j, j) $ into heap.
Increment $ j $.
2. Pop the flight $ i $ with maximum $ c_i $ from heap.
3. Assign $ t_i = t $.
4. Record $ t_i $ for flight $ i $.
After processing all $ t $, compute total cost:
$$
\sum_{i=1}^{n} c_i \cdot (t_i - i)
$$
Output:
- First line: total cost
- Second line: $ t_1, t_2, \dots, t_n $ (in original flight order)
---
**Final Formal Statement:**
Let $ \mathcal{T} = \{k+1, k+2, \dots, k+n\} $.
Find a bijection $ t: \{1,\dots,n\} \to \mathcal{T} $ such that:
- $ t(i) \geq i $ for all $ i \in \{1,\dots,n\} $,
- and $ \sum_{i=1}^n c_i \cdot t(i) $ is minimized.
This is achieved by the greedy algorithm above:
At each time slot $ t \in \mathcal{T} $, assign the unassigned flight $ i $ with $ i \leq t $ and maximum $ c_i $ to $ t $.
**Output:**
- Minimum total cost: $ \sum_{i=1}^n c_i (t_i - i) $
- Schedule: $ t_1, t_2, \dots, t_n $ (in flight index order)