CF853A.Planning

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.

海伦在大都会机场工作，负责制定航班离港时刻表。今天共有 $n$ 个航班需要离港，其中第 $i$ 个航班原计划在当天的第 $i$ 分钟离港。

大都会机场是大都会国的主要交通枢纽，因此维持原定时刻表十分困难。今天的情况正是如此：由于技术故障，当天最初的 $k$ 分钟内没有任何航班能够离港，因此现在必须重新制定离港时刻表。

所有 $n$ 个原定航班现在必须在第 $(k+1)$ 分钟至第 $(k+n)$ 分钟（含）之间的不同分钟时刻离港。不过，航班离港的顺序不必与原计划顺序一致——新时刻表中的顺序可以不同。唯一限制是：任何航班的离港时间不得早于其原计划离港时间。

海伦知道，第 $i$ 个航班每延误一分钟，机场将损失 $c_i$ 卢布。请帮助她确定新时刻表中各航班的离港顺序，使得机场的总损失最小。

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.

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 300\,000$），其中 $n$ 表示航班数量，$k$ 表示一天开始时航班未起飞的分钟数。

第二行包含 $n$ 个整数 $c_1,\,c_2,\,...,\,c_n$（$1 \leq c_i \leq 10^7$），其中 $c_i$ 表示将第 $i$ 个航班延迟一分钟的代价。

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.

第一行必须包含延迟航班的最小可能总成本。

第二行必须包含 $n$ 个互不相同的整数 $t_1,\,t_2,\,...,\,t_n$（满足 $k\,+\,1\,\leq\,t_i\,\leq\,k\,+\,n$），其中 $t_i$ 表示第 $i$ 个航班必须起飞的时间（单位：分钟）。若存在多个最优调度方案，输出任意一个即可。

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.

我们来考虑样例测试。如果海伦只是将所有航班统一延后 2 分钟（保持原有顺序不变），则航班延误的总代价为 $(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38$ burles。

然而，更优的调度方案如样例答案所示，其代价为 $(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20$ burles。