English · Original
Chinese · Translation
Formal · Original
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 ≤ 10^7]），其中 #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 ≤ 10^7]），其中 #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] 布尔。
Let $ n $ and $ k $ be positive integers with $ 1 \leq k \leq n \leq 300{,}000 $.
Let $ c = (c_1, c_2, \dots, c_n) $ be a sequence of positive integers representing the cost per minute of delay for each flight, where $ 1 \leq c_i \leq 10^7 $.
Each flight $ i $ was originally scheduled to depart at minute $ i $, but the first $ k $ minutes are unavailable.
The new departure times must be $ n $ distinct integers chosen from the set $ \{k+1, k+2, \dots, k+n\} $, and for each flight $ i $, its new departure time $ t_i $ must satisfy $ t_i \geq i $.
The total cost is defined as:
$$
\sum_{i=1}^n c_i \cdot (t_i - i)
$$
**Objective:**
Minimize the total cost $ \sum_{i=1}^n c_i (t_i - i) $, subject to:
- $ t_i \in \{k+1, k+2, \dots, k+n\} $,
- $ t_i \neq t_j $ for all $ i \neq j $,
- $ t_i \geq i $ for all $ i $.
**Output:**
- The minimum total cost.
- A sequence $ (t_1, t_2, \dots, t_n) $ achieving this minimum.
API Response (JSON)
{
"problem": {
"name": "C. Planning",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF854C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Helen 在 Metropolis 机场工作，负责制定起飞时刻表。今天有 #cf_span[n] 架航班必须起飞，第 #cf_span[i] 架航班原计划在当天第 #cf_span[i] 分钟起飞。\n\n由于 Metropolis 机场是 Metropolia 的主要交通枢纽，维持时刻表十分困难。今天正是如此：由于技术问题，当天的前 #cf_span[k] 分钟内没有任何航班起飞，因此必须制定新的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ and $ k $ be positive integers with $ 1 \\leq k \\leq n \\leq 300{,}000 $. \nLet $ c = (c_1, c_2, \\dots, c_n) $ be a sequence of positive integers representing the cost per minute of delay for ...",
"is_translate": false,
"language": "Formal"
}
]
}