CF853A Planning

Helen 在大都会机场工作，她的任务是安排每天的航班起飞时刻。今天一共有 $n$ 架飞机将要起飞，第 $i$ 架飞机将在第 $i$ 分钟起飞。 大都会机场是大都会最重要的交通枢纽，因此想要原封不动地按照起飞时刻表的时刻起飞是很困难的。今天的情况也是如此：由于技术原因，在今天一开始的 $k$ 分钟内飞机不允许起飞，因此必须创建一个新的起飞时刻表。 所有的航班必须在第 $(k+1)$ 分钟到第 $(k+n)$ 分钟内（包括两端）起飞，而且每分钟仅能有一架飞机起飞。然而，航班起飞的先后顺序可以与最初的时刻表排好的顺序不同，重排的时刻表只有一个限制：飞机不能比它在初始时刻表中起飞的时刻还要早的时刻起飞（即：第 $i$ 架飞机必须在第 $i$ 分钟后或第 $i$ 分钟时起飞）。 Helen 知道第 $i$ 架飞机起飞时刻每延误一分钟机场所需支付的额外花费 $c_i$ 是多少。帮助她找到额外花费最小的方案。

输入数据的第一行包括两个整数 $n$ 和 $k$（$1\le k\le n\le 3\times 10^5$）。 第二行包括 $n$ 个整数 $c_1,c_2,\dots,c_n$（$1\le c_i\le 10^7$）。

输出数据的第一行包括一个整数，表示最小额外花费。 第二行包括 $n$ 个整数 $t_1,t_2,\dots,t_n$（$k+1\le t_i\le k+n$），$t_i$ 表示第 $i$ 架航班起飞的时刻。如果同时存在多种方案，输出任意一种。

在样例中，如果 Helen 仅把每架飞机的起飞时刻都推迟 $2$ 分钟，那么总额外花费是 $38$。 但是，对于最佳结果来说，总额外花费为 $20$。 感谢 @radish布団 提供的翻译。