Planning

题意翻译

Helen在大都会机场工作，她的任务是安排每天的航班起飞时刻。今天一共有n架飞机将要起飞，第i架飞机将在第i分钟起飞。 大都会机场是大都会最重要的交通枢纽，因此想要原封不动地按照起飞时刻表的时刻起飞是很困难的。今天的情况也是如此：由于技术原因，在今天一开始的k分钟内飞机不允许起飞，因此必须创建一个新的起飞时刻表。 所有的航班必须在第(k+1)分钟到第(k+n)分钟内(包括两端)起飞，而且每分钟仅能有一架飞机起飞。然而，航班起飞的先后顺序可以与最初的时刻表排好的顺序不同，重排的时刻表只有一个限制：飞机不能比它在初始时刻表中起飞的时刻还要早的时刻起飞(即：第i架飞机必须在第i分钟后或第i分钟时起飞)。 Helen知道第i架飞机起飞时刻每延误一分钟机场所需支付的额外花费ci是多少。帮助她找到额外花费最小的方案。 输入格式： 输入数据的第一行包括两个整数n和k(1<=k<=n<=300000)。 第二行包括n个整数c1，c2，...，cn(1<=ci<=10^7). 输出格式： 输出数据的第一行包括一个整数，表示最小额外花费。 第二行包括n个整数t1，t2，...，tn(k+1<=ti<=k+n)，ti表示第i架家航班起飞的时刻。如果同时存在多种方案，输出任意一种。 说明： 在样例中，如果Helen仅把每架飞机的起飞时刻都推迟2分钟，那么总额外花费是38。 但是，对于最佳结果来说，总额外花费为20。 感谢@radish布団 提供的翻译

题目描述

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.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=k<=n<=300000 $ ), 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}<=10^{7} $ ), here $ c_{i} $ is the cost of delaying the $ i $ -th flight for one minute.

输出格式

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.

输入输出样例

输入样例 #1

5 2
4 2 1 10 2

输出样例 #1

20
3 6 7 4 5 

说明

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.