{"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":"\u003cp\u003eDiego y su equipo están muy contentos, pues clasificaron a las World Finals de la ICPC 2020, a realizarse en Moscú. Lamentablemente, no tienen la ayuda financiera para costearse el viaje, así que decidieron trabajar en lo que mejor saben hacer: programar. En el trabajo, les dieron el siguiente problema:\u003c/p\u003e\n\u003cp\u003eDado un arreglo \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?p\" alt\u003d\"p\" title\u003d\"p\" /\u003e de \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?n\" alt\u003d\"n\" title\u003d\"n\" /\u003e enteros \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?p_1%2C%20p_2%2C%20...%2C%20p_n\" alt\u003d\"p_1, p_2, ..., p_n\" title\u003d\"p_1, p_2, ..., p_n\" /\u003e, debes escoger \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?k\" alt\u003d\"k\" title\u003d\"k\" /\u003e pares de enteros:\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cp\u003e\u003cbr /\u003e\u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?%0A%5Bl_1%2C%20r_1%5D%2C%20%5Bl_2%2C%20r_2%5D%2C%20...%2C%20%5Bl_k%2C%20r_k%5D%20%281%20%5Cleq%20l_1%20%5Cleq%20r_1%20%3C%20l_2%20%5Cleq%20r_2%20%3C%20...%20%3C%20l_k%20%5Cleq%20r_k%29%0A\" alt\u003d\"\n[l_1, r_1], [l_2, r_2], ..., [l_k, r_k] (1 \\leq l_1 \\leq r_1 \u0026lt; l_2 \\leq r_2 \u0026lt; ... \u0026lt; l_k \\leq r_k)\n\" title\u003d\"\n[l_1, r_1], [l_2, r_2], ..., [l_k, r_k] (1 \\leq l_1 \\leq r_1 \u0026lt; l_2 \\leq r_2 \u0026lt; ... \u0026lt; l_k \\leq r_k)\n\" /\u003e\u003cbr /\u003e\u003c/center\u003e\n\n en donde cada par representa un índices de un subarreglo que empieza en \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?l_i\" alt\u003d\"l_i\" title\u003d\"l_i\" /\u003e y termina en \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?r_i\" alt\u003d\"r_i\" title\u003d\"r_i\" /\u003e.\u003c/p\u003e\n\u003cp\u003eLos \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?k\" alt\u003d\"k\" title\u003d\"k\" /\u003e subarreglos deben ser disjuntos, es decir, no puede haber un elemento del arreglo perteneciente a dos subarreglos escogidos al mismo tiempo. También, todos los subarreglos deben tener exactamente \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?m\" alt\u003d\"m\" title\u003d\"m\" /\u003e elementos (\u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?r_i%20-%20l_i%20%2B%201%20%3D%20m\" alt\u003d\"r_i - l_i + 1 \u003d m\" title\u003d\"r_i - l_i + 1 \u003d m\" /\u003e para todo \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?i\" alt\u003d\"i\" title\u003d\"i\" /\u003e).\u003c/p\u003e\n\u003cp\u003eSe quiere saber el máximo valor posible de la suma de todos los elementos escogidos. Es decir,\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cp\u003e\u003cbr /\u003e\u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?%0A%5Csum_%7Bi%3D1%7D%5Ek%20%5Csum_%7Bj%3Dl_i%7D%5E%7Br_i%7D%20p_j%0A\" alt\u003d\"\n\\sum_{i\u003d1}^k \\sum_{j\u003dl_i}^{r_i} p_j\n\" title\u003d\"\n\\sum_{i\u003d1}^k \\sum_{j\u003dl_i}^{r_i} p_j\n\" /\u003e\u003cbr /\u003e\u003c/p\u003e\u003c/center\u003e\n\n\u003cp\u003eLamentablemente, el fuerte del equipo de Diego no es programación dinámica, así que necesita de tu ayuda para poder viajar a Moscú.\u003c/p\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eLa primera línea contiene tres enteros \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?n\" alt\u003d\"n\" title\u003d\"n\" /\u003e, \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?m\" alt\u003d\"m\" title\u003d\"m\" /\u003e y \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?k\" alt\u003d\"k\" title\u003d\"k\" /\u003e (\u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?1%20%5Cleq%20m%5Ccdot%20k%20%5Cleq%20n%20%5Cleq%205000\" alt\u003d\"1 \\leq m\\cdot k \\leq n \\leq 5000\" title\u003d\"1 \\leq m\\cdot k \\leq n \\leq 5000\" /\u003e).\u003c/p\u003e\n\u003cp\u003eLa segunda línea contiene \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?n\" alt\u003d\"n\" title\u003d\"n\" /\u003e enteros \u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?p_1%2C%20p_2%2C%20...%2C%20p_n\" alt\u003d\"p_1, p_2, ..., p_n\" title\u003d\"p_1, p_2, ..., p_n\" /\u003e (\u003cimg style\u003d\"vertical-align:middle\" src\u003d\"https://latex.codecogs.com/png.latex?0%20%5Cleq%20p_i%20%5Cleq%2010%5E9\" alt\u003d\"0 \\leq p_i \\leq 10^9\" title\u003d\"0 \\leq p_i \\leq 10^9\" /\u003e).\u003c/p\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eImprime un entero en una sola línea – el máximo valor posible de la suma.\u003c/p\u003e\n"}},{"title":"Examples","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 1\u003cbr\u003e1 2 3 4 5\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\u003e9\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e7 1 3\u003cbr\u003e2 10 7 18 5 33 0\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\u003e61\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}