Debes programar $n$ trabajos en una línea de procesamiento. Los trabajos forman una secuencia, y el trabajo $i$ tiene una carga de trabajo $a_i$. La línea de procesamiento consta de $m$ etapas en serie.
Antes de que comience el procesamiento, puedes elegir un entero $t$ ($0\le t\le n$). Esto mueve los primeros $t$ trabajos al final sin cambiar su orden relativo, obteniendo $a_{t+1},a_{t+2},\ldots,a_n,a_1,a_2,\ldots,a_t$. Elegir $t=0$ o $t=n$ deja la secuencia sin cambios.
A continuación, debes dividir la secuencia resultante en, como máximo, $k$ segmentos contiguos no vacíos, cada uno de los cuales forma un lote. La carga de trabajo de un lote es la suma de las cargas de trabajo de sus trabajos.
Los lotes entran entonces en la línea de procesamiento en orden. Cada lote pasa por las etapas $1,2,\ldots,m$ en este orden, y en cada etapa tarda un tiempo igual a su carga de trabajo. Cada etapa procesa como máximo un lote a la vez, siguiendo el orden de izquierda a derecha de los lotes en la secuencia. Tras terminar en una etapa, un lote puede esperar a que la siguiente etapa esté disponible. Mientras espera, ya no ocupa la etapa anterior, que puede procesar el siguiente lote. Distintas etapas pueden procesar distintos lotes simultáneamente.
La línea de procesamiento comienza a procesar en el instante $0$. Elige el prefijo que se moverá y la división en lotes de modo que todos los trabajos terminen lo antes posible.
Entrada
La primera línea contiene tres enteros $n,m,k$ ($1\le n,m\le 5\times 10^5$, $1\le k\le n$): el número de trabajos, el número de etapas y el número máximo de lotes.
La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^6$), las cargas de trabajo de los trabajos.
Salida
Imprime un entero: el mínimo instante posible en el que todos los trabajos hayan terminado.
Ejemplos
Entrada 1
4 3 2 3 1 4 2
Salida 1
20
Nota
Una elección óptima es mover el prefijo $[3,1,4]$ al final, obteniendo la secuencia $[2,3,1,4]$, y dividirla en dos lotes $[2,3]$ y $[1,4]$. Ambos lotes tienen una carga de trabajo de $5$. Pueden comenzar en la primera etapa en los instantes $0$ y $5$, y terminar en la tercera etapa en los instantes $15$ y $20$, respectivamente. Por tanto, todos los trabajos terminan en el instante $20$, que es el mínimo instante posible.