{"trustable":true,"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e火星政府不仅对优化太空飞行感兴趣,还希望改善行星的道路系统。\u003c/p\u003e\u003cp\u003e火星最重要的高速公路之一连接着奥林匹克城和西多洛普,西多洛普是赛德尼亚的首都。在这个问题中,我们只考虑从西多洛普到奥林匹克城的路线,而不考虑反向路线(即从奥林匹克城到西多洛普的路线)。\u003c/p\u003e\u003cp\u003e从西多洛普到奥林匹克城的道路长$$$\\ell$$$公里。道路上的每个点都有一个坐标$$$x$$$($$$0 \\le x \\le \\ell$$$),表示距离西多洛普的公里数。因此,西多洛普位于坐标$$$0$$$的点上,奥林匹克城位于坐标$$$\\ell$$$的点上。\u003c/p\u003e\u003cp\u003e道路上有$$$n$$$个路标,其中第$$$i$$$个设置了速度限制$$$a_i$$$。这个限制意味着下一公里必须在$$$a_i$$$分钟内通过,并且在遇到下一个路标之前一直有效。在道路起点(即坐标为$$$0$$$的点)有一个路标,它设置了初始速度限制。\u003c/p\u003e\u003cp\u003e如果你知道所有路标的位置,计算从西多洛普到奥林匹克城的行驶时间并不难。考虑一个例子:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ea1f9c096794e139328bb0162cd91966?v\u003d1718601163\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"756px\"\u003e \u003c/center\u003e\u003cp\u003e在这个例子中,你需要以每五分钟行驶前三公里,然后以八分钟行驶一公里,接着以每三分钟行驶四公里,最后两公里必须以每六分钟行驶。总时间为$$$3\\cdot 5 + 1\\cdot 8 + 4\\cdot 3 + 2\\cdot 6 \u003d 47$$$分钟。\u003c/p\u003e\u003cp\u003e为了优化道路交通,火星政府决定最多移除$$$k$$$个路标。不能移除道路起点的路标,否则起点将没有限速。通过移除这些路标,政府还希望使从西多洛普到奥林匹克城的行驶时间尽可能缩短。\u003c/p\u003e\u003cp\u003e最大的工业企业位于赛德尼亚,因此优化从奥林匹克城到西多洛普的道路交通是优先任务。因此,火星政府希望你按照上述方式移除路标。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个整数$$$n$$$、$$$\\ell$$$、$$$k$$$($$$1 \\le n \\le 500$$$、$$$1 \\le \\ell \\le 10^5$$$、$$$0 \\le k \\le n-1$$$),表示道路上的路标数量、城市之间的距离和你可以移除的最大路标数。\u003c/p\u003e\u003cp\u003e第二行包含$$$n$$$个整数$$$d_i$$$($$$d_1 \u003d 0$$$、$$$d_i \u0026lt; d_{i+1}$$$、$$$0 \\le d_i \\le \\ell - 1$$$),表示所有路标的坐标。\u003c/p\u003e\u003cp\u003e第三行包含$$$n$$$个整数$$$a_i$$$($$$1 \\le a_i \\le 10^4$$$),表示速度限制。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数,表示如果你最多移除$$$k$$$个路标,从西多洛普到奥林匹克城的最短行驶时间(以分钟为单位)。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 10 0\n0 3 4 8\n5 8 3 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e47\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 10 2\n0 3 4 8\n5 8 3 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e38\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,你不能移除路标。因此答案是$$$47$$$,正如上述陈述中所说。\u003c/p\u003e\u003cp\u003e在第二个示例中,你可以移除第二个和第四个路标。在这种情况下,你需要以$$$4\\cdot5 \u003d 20$$$分钟行驶四公里,然后以$$$6\\cdot3 \u003d 18$$$分钟行驶六公里,因此总时间为$$$4\\cdot5 + 6\\cdot3 \u003d 38$$$分钟。\u003c/p\u003e"}}]}