{"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\u003eO Governo de Marte não está apenas interessado em otimizar voos espaciais, mas também deseja melhorar o sistema rodoviário do planeta.\u003c/p\u003e\u003cp\u003eUma das rodovias mais importantes de Marte conecta a Cidade de Olímpia e Kstolop, a capital de Cydonia. Neste problema, consideramos apenas o caminho de Kstolop para a Cidade de Olímpia, mas não o caminho inverso (ou seja, o caminho da Cidade de Olímpia para Kstolop).\u003c/p\u003e\u003cp\u003eA estrada de Kstolop para a Cidade de Olímpia tem $$$\\ell$$$ quilômetros de comprimento. Cada ponto da estrada tem uma coordenada $$$x$$$ ($$$0 \\le x \\le \\ell$$$), que é igual à distância de Kstolop em quilômetros. Assim, Kstolop está localizado no ponto com coordenada $$$0$$$, e a Cidade de Olímpia está localizada no ponto com coordenada $$$\\ell$$$.\u003c/p\u003e\u003cp\u003eHá $$$n$$$ placas ao longo da estrada, a $$$i$$$-ésima das quais define um limite de velocidade $$$a_i$$$. Este limite significa que o próximo quilômetro deve ser percorrido em $$$a_i$$$ minutos e está ativo até você encontrar o próximo ao longo da estrada. Há uma placa de estrada no início da estrada (ou seja, no ponto com coordenada $$$0$$$), que define o limite de velocidade inicial.\u003c/p\u003e\u003cp\u003eSe você conhece a localização de todas as placas, não é difícil calcular quanto tempo leva para dirigir de Kstolop para a Cidade de Olímpia. Considere um exemplo:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ea1f9c096794e139328bb0162cd91966?v\u003d1711688026\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"756px\"\u003e \u003c/center\u003e\u003cp\u003eAqui, você precisa dirigir os primeiros três quilômetros em cinco minutos cada, depois um quilômetro em oito minutos, depois quatro quilômetros em três minutos cada, e finalmente os dois últimos quilômetros devem ser percorridos em seis minutos cada. O tempo total é de $$$3\\cdot 5 + 1\\cdot 8 + 4\\cdot 3 + 2\\cdot 6 \u003d 47$$$ minutos.\u003c/p\u003e\u003cp\u003ePara otimizar o tráfego rodoviário, o Governo de Marte decidiu remover no máximo $$$k$$$ placas de sinalização. Não pode remover a placa no início da estrada, caso contrário, não haverá limite no início. Ao remover essas placas, o Governo também deseja tornar o tempo necessário para dirigir de Kstolop para a Cidade de Olímpia o mais curto possível.\u003c/p\u003e\u003cp\u003eAs maiores empresas industriais estão localizadas em Cydonia, então a tarefa prioritária é otimizar o tráfego rodoviário a partir da Cidade de Olímpia. Portanto, o Governo de Marte deseja que você remova as placas da maneira descrita acima.\u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eA primeira linha contém três inteiros $$$n$$$, $$$\\ell$$$, $$$k$$$ ($$$1 \\le n \\le 500$$$, $$$1 \\le \\ell \\le 10^5$$$, $$$0 \\le k \\le n-1$$$), a quantidade de placas na estrada, a distância entre as cidades e o número máximo de placas que você pode remover.\u003c/p\u003e\u003cp\u003eA segunda linha contém $$$n$$$ inteiros $$$d_i$$$ ($$$d_1 \u003d 0$$$, $$$d_i \u0026lt; d_{i+1}$$$, $$$0 \\le d_i \\le \\ell - 1$$$) — coordenadas de todas as placas.\u003c/p\u003e\u003cp\u003eA terceira linha contém $$$n$$$ inteiros $$$a_i$$$ ($$$1 \\le a_i \\le 10^4$$$) — limites de velocidade.\u003c/p\u003e"}},{"title":"Saída","value":{"format":"HTML","content":"\u003cp\u003eImprima um único inteiro — tempo mínimo possível para dirigir de Kstolop para a Cidade de Olímpia em minutos, se você remover no máximo $$$k$$$ placas de sinalização.\u003c/p\u003e"}},{"title":"Exemplo 1","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":"Exemplo 2","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":"Nota","value":{"format":"HTML","content":"\u003cp\u003eNo primeiro exemplo, você não pode remover as placas. Portanto, a resposta é $$$47$$$, como é dito nas declarações acima.\u003c/p\u003e\u003cp\u003eNo segundo exemplo, você pode remover a segunda e a quarta placa. Nesse caso, você precisa dirigir quatro quilômetros em $$$4\\cdot5 \u003d 20$$$ minutos, e depois seis quilômetros em $$$6\\cdot3 \u003d 18$$$, então o tempo total é de $$$4\\cdot5 + 6\\cdot3 \u003d 38$$$ minutos.\u003c/p\u003e"}}]}