{"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\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 marciano está empenhado em aprimorar não apenas os voos espaciais, mas também o sistema viário do planeta.\u003c/p\u003e\n\u003cp\u003eUma das estradas vitais de Marte liga Campina Pequena a João Pessoa, a capital de Parayhba. Neste desafio, estamos considerando apenas o percurso de João Pessoa para Campina Pequena, excluindo o caminho oposto (ou seja, de Campina Pequena para João Pessoa).\u003c/p\u003e\n\u003cp\u003eA rodovia de João Pessoa para Campina Pequena tem um comprimento de $$$\\ell$$$ quilômetros. Cada ponto da estrada é marcado com uma coordenada $$$x$$$ ($$$0 \\le x \\le \\ell$$$), representando a distância em quilômetros a partir de João Pessoa. Assim, João Pessoa está localizada na coordenada $$$0$$$, enquanto Campina Pequena está na coordenada $$$\\ell$$$.\u003c/p\u003e\n\u003cp\u003eExistem $$$n$$$ sinais ao longo da estrada, onde o $$$i$$$-ésimo sinal indica um limite de velocidade de $$$a_i$$$ minutos para percorrer o próximo quilômetro, permanecendo ativo até encontrar o próximo sinal na estrada. O primeiro sinal está no início da estrada (ou seja, na coordenada $$$0$$$), definindo o limite inicial de velocidade.\u003c/p\u003e\n\u003cp\u003eCom a localização de todos os sinais conhecida, é possível calcular o tempo total de viagem de João Pessoa para Campina Pequena. Considere o seguinte exemplo:\u003c/p\u003e\n\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\n\u003cp\u003eNeste caso, os primeiros três quilômetros devem ser percorridos em cinco minutos cada, seguidos de um quilômetro em oito minutos, quatro quilômetros em três minutos cada, e os dois quilômetros finais 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\n\u003cp\u003eVisando otimizar o tráfego, o governo marciano decidiu remover no máximo $$$k$$$ sinais de trânsito. A remoção do sinal no início da estrada não é permitida, pois isso resultaria na ausência de um limite inicial. A remoção dos sinais deve ser feita de forma a minimizar o tempo total de viagem de João Pessoa para Campina Pequena.\u003c/p\u003e\n\u003cp\u003eCom as principais indústrias localizadas em Parayhba, a prioridade é otimizar o tráfego rodoviário saindo de Campina Pequena. Portanto, o governo de Marte solicita que os sinais sejam removidos conforme descrito 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 Campina Pequena para a João Pessoa 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"}}]}