海伦在大都会机场工作。她负责制定出发时间表。今天有 n 个航班必须起飞,其中第 i 个航班计划在当天的第 i 分钟起飞。
大都会机场是大都会的主要交通枢纽,因此很难保持航班完好无损。今天的情况正是如此:由于技术问题,当天的前 k 分钟内没有航班能够起飞,因此现在必须创建新的起飞时间表。
现在,所有 n 个定期航班必须在第 (k + 1) 次和第 (k + n) 次(含)之间的不同分钟出发。不过,航班并非强制按照最初安排的顺序出发,新时刻表中的顺序可能会有所不同。只有一个限制:任何航班不得早于最初计划的起飞时间起飞。
Helen 知道第 i 个航班每延误一分钟就会花费机场 ci burles。帮助她找到新时刻表中出发的航班顺序,从而最大限度地降低机场的总成本。
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 300 000),其中 n 是航班数量,k 是当天开始时航班未起飞的分钟数。
第二行包含n个整数c1, c2, ..., cn (1 ≤ ci ≤ 107),这里ci是第i个航班延误一分钟的成本。
输出
第一行必须包含航班延误的最小可能总成本。
第二行必须包含n个不同的整数t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n),这里ti是第i个航班必须起飞的分钟。如果有多个最佳时间表,请打印其中任何一个。
示例
输入 #1
5 2 4 2 1 10 2
输出 #1
20 3 6 7 4 5
注意
让我们考虑样本测试。如果 Helen 在 2 分钟后将所有航班移至 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。