{"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":"HTML","content":"qnjj 在大都会机场工作,她的任务是安排每天的航班起飞时刻。今天一共有 $n$ 架飞机将要起飞,第 $i$ 架飞机将在第 $i$ 分钟起飞。\u003cbr\u003e\n\n大都会机场是大都会最重要的交通枢纽,因此想要原封不动地按照起飞时刻表的时刻起飞是很困难的。今天的情况也是如此:由于技术原因,在今天一开始的k分钟内飞机不允许起飞,因此必须创建一个新的起飞时刻表。\u003cbr\u003e\n\n所有的航班必须在第 $(k+1)$ 分钟到第 $(k+n)$ 分钟内(包括两端)起飞,而且每分钟仅能有一架飞机起飞。然而,航班起飞的先后顺序可以与最初的时刻表排好的顺序不同,重排的时刻表只有一个限制:飞机不能比它在初始时刻表中起飞的时刻还要早的时刻起飞(即:第 $i$ 架飞机必须在第 $i$ 分钟后或第 $i$ 分钟时起飞)。\u003cbr\u003e\n\nqnjj 知道第 $i$ 架飞机起飞时刻每延误一分钟机场所需支付的额外花费 $c_i$ 是多少。帮助她找到额外花费最小的方案。\u003cbr\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"输入数据的第一行包括两个整数 $n$ 和 $k(1\u003c\u003dk\u003c\u003dn\u003c\u003d300000)$\u003cbr\u003e\n\n第二行包括 $n$ 个整数 $c_1,c_2,...,c_n(1\u003c\u003dc_i\u003c\u003d10^7)$"}},{"title":"Output","value":{"format":"HTML","content":"输出数据的第一行包括一个整数,表示最小额外花费。\u003cbr\u003e\n\n第二行包括 $n$ 个整数 $t_1,t_2,...,t_n(k+1\u003c\u003dt_i\u003c\u003dk+n)$,$t_i$ 表示第 $i$ 架家航班起飞的时刻。\u003cbr\u003e如果同时存在多种方案,输出任意一种。"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5 2\u003cbr\u003e4 2 1 10 2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e20\u003cbr\u003e3 6 7 4 5 \u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"在样例中,如果 qnjj 仅把每架飞机的起飞时刻都推迟2分钟,那么总额外花费是 $38$。\u003cbr\u003e 但是,对于最佳结果来说,总额外花费为 $20$。\n\n"}}]}