{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Jane是一个很有责任心的机场工作人员,她的职责就是安排好飞机飞行时刻表。今天将会有n架飞机起飞,第i架飞机预计离开时间是当天的第i分钟。\n由于Jane工作的机场是当地的主要机场,流量极大,难免要发生一些意外事故。恰巧今天机场的某些重要机器出现了问题,需要k分钟进行修理,也就是说,在前k分钟,所有的飞机都无法起飞,原来的飞行时刻表必须修改。\n所有预计飞离的飞机必须要在(k+1)至(k+n)分钟的不同时刻起飞。但是,飞离的顺序不需要和一开始的顺序相同,换言之,新的飞行时刻表是可以和最初的飞行时刻表不一样的。由于事发突然,无法快速通知所有乘客,如果飞机提早离开机场,会造成乘客不满,所以,所有飞机新的离开时刻不能早于原定的时刻。\nJane知道第i架飞机每延迟1分钟,就会造成ci点损失,请帮助她安排新的飞行时刻表,使得造成的损失总和最小"}},{"title":"Input","value":{"format":"MD","content":"第一行包含两个正整数n和k,1\u003c\u003dk\u003c\u003dn\u003c\u003d300000,n是预计起飞的飞机总数,k表示前k分钟不可以起飞。\n第二行包含n个正整数c1,c2,...,cn(1\u003c\u003dci\u003c\u003d10000000),ci是第i架飞机每延迟1分钟会造成的损失"}},{"title":"Output","value":{"format":"MD","content":"第一行仅输出一个数,为最小的损失总和\n第二行输出n个互不相同的数,t1,t2,...,tn(k+1\u003c\u003dti\u003c\u003dk+n),ti是第i架飞机起飞的时刻。如果有多种方案,任意输出一种即可。"}},{"title":"Sample Input","value":{"format":"MD","content":"```\n5 2 \n4 2 1 10 2\n```"}},{"title":"Sample Output","value":{"format":"MD","content":"```\n20 \n3 6 7 4 5 \n```"}},{"title":"Note","value":{"format":"MD","content":"对于样例,如果Jane将所有飞机的起飞时刻延迟2分钟,那么造成的损失为 \n(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 \u003d 38 \n如果Jane让第1...5架飞机分别在第3,6,7,4,5分钟起飞,那么造成的损失为\n(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 \u003d 20\n显然第二种方案更好"}}]}