{"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 the day.\n\nMetropolis 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.\n\nAll _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.\n\nHelen 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.\n\n## Input\n\nThe 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.\n\nThe 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.\n\n## Output\n\nThe first line must contain the minimum possible total cost of delaying the flights.\n\nThe 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.\n\n[samples]\n\n## Note\n\nLet 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.\n\nHowever, 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.","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] 分钟内没有任何航班起飞，因此必须制定新的起飞时刻表。\n\n所有 #cf_span[n] 架原定航班现在必须在第 #cf_span[(k + 1)] 分钟到第 #cf_span[(k + n)] 分钟（含）之间，选择不同的分钟起飞。然而，航班的起飞顺序可以与原计划不同，唯一限制是：任何航班不得比原计划更早起飞。\n\nHelen 知道，第 #cf_span[i] 架航班每延误一分钟，机场将损失 #cf_span[ci] 布尔。请帮助她确定新的起飞顺序，使机场的总延误成本最小。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 300 000]），其中 #cf_span[n] 是航班数量，#cf_span[k] 是当天开始时航班未能起飞的分钟数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 10^7]），其中 #cf_span[ci] 表示第 #cf_span[i] 架航班每延误一分钟的成本。\n\n第一行必须输出航班延误的最小可能总成本。\n\n第二行必须输出 #cf_span[n] 个不同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 架航班的起飞分钟。如果有多个最优方案，输出任意一个即可。\n\n考虑样例测试：如果 Helen 将所有航班整体推迟 2 分钟并保持原有顺序，则总延误成本为 #cf_span[(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38] 布尔。\n\n但更好的方案如样例答案所示，其成本为 #cf_span[(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20] 布尔。\n\n## Input\n\n第一行包含两个整数 #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] 架航班每延误一分钟的成本。\n\n## Output\n\n第一行必须输出航班延误的最小可能总成本。第二行必须输出 #cf_span[n] 个不同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 架航班的起飞分钟。如果有多个最优方案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n考虑样例测试：如果 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] 布尔。","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 each flight, where $ 1 \\leq c_i \\leq 10^7 $.\n\nEach flight $ i $ was originally scheduled to depart at minute $ i $, but the first $ k $ minutes are unavailable.  \nThe 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 $.\n\nThe total cost is defined as:\n$$\n\\sum_{i=1}^n c_i \\cdot (t_i - i)\n$$\n\n**Objective:**  \nMinimize the total cost $ \\sum_{i=1}^n c_i (t_i - i) $, subject to:\n- $ t_i \\in \\{k+1, k+2, \\dots, k+n\\} $,\n- $ t_i \\neq t_j $ for all $ i \\neq j $,\n- $ t_i \\geq i $ for all $ i $.\n\n**Output:**  \n- The minimum total cost.\n- A sequence $ (t_1, t_2, \\dots, t_n) $ achieving this minimum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF854C","tags":[],"sample_group":[["5 2\n4 2 1 10 2","20\n3 6 7 4 5"]],"created_at":"2026-03-03 11:00:39"}}