El negocio ha sido lento en el la venta de autos usados. En un esfuerzo por atraer a nuevos clientes, la administración ha creado el Programa de Incentivos de Reembolso de Diversión Fabulosa. Este es un juego simple que permite a los clientes para tratar de ganar un descuento en la compra de un automóvil. Es un juego de mesa donde se marca cada cuadrado con la cantidad de la rebaja. El cliente avanza haciendo girar una ruleta. Cada cuadro se cae en una casilla se suma a su cantidad marcada. Cuando llega al extremo del tablero se ve recompensado con la cantidad del reembolso total.

Por supuesto, dada la empresa en cuestión, no debería ser ninguna sorpresa que hay un par de condiciones por escrito y en la letra muy pequeña. La primera es que hay un límite para el número de intentos que el cliente tiene que terminar el juego, si no llega a la final en el número asignado de intentos entonces pierde su reembolso. La segunda es que algunas de las casillas en realidad tienen un valor negativo que resta en lugar de añadir. Un cliente en particular con mala suerte, incluso puede salir del juego con un descuento negativo.

A pesar de estas condiciones, a la gerencia le preocupa que alguien pueda ganar una gran rebaja en particular, algo que les gustaría evitar a toda costa. Su trabajo es tomar una configuración especial para el juego y decidir el descuento máximo que un cliente podría obtener.

Consideremos, por ejemplo, el tablero de juego siguiente:

Supongamos que tenemos 5 vueltas para terminar el juego, y cada vez nos podemos mover entre 1 y 4 espacios en función de lo que hacemos girar. Tenga en cuenta que tenemos que empezar justo antes de la primera casilla, por lo que gira a 1 nos lleva a la primera casilla. Observe también que debemos poner fin al caer más allá del final de la última casilla. No tiene por qué ser exacta, es suficiente cualquier número que nos lleva fuera del tablero.

La ilustración muestra dos maneras diferentes. Es posible que el juego podría ir siguiendo las flechas en la parte superior, si hacemos girar un 2, 3, 4, 1, 1, respectivamente, que va a ganar un reembolso total de 50 + 30 + 20 + 70 = 170. Sin embargo, la rebaja mejor que podíamos ganar sería de 220. Esta cantidad se obtiene, si se giró la ruleta 1, 3, 2, 4, 1, respectivamente, como se muestra por el camino inferior. Tenga en cuenta que si tomamos todos las casillas con un número positivo, no habríamos sido capaces de llegar a la final de la tabla antes de 5 vueltas.

La ilustración siguiente: 

muestra un juego donde tenemos 4 vueltas para terminar el juego, y puede mover hasta 3 plazas en cada turno. Una vez más, se muestran dos caminos diferentes, el de arriba ganan un descuento de −150, y el de abajo −100. De hecho, −100 es el descuento más alto que puede ganar en este juego (un hecho que sin duda agradará a la gestión de la empresa). Por supuesto, también puede haber una secuencia de movimientos en los que no llegamos a la final por ejemplo, limitar la girar un 1 cada vez. A pesar de no haber terminado en realidad sería preferible terminar con un descuento negativo, este problema sólo vamos a considerar las secuencias de movimientos que nos permiten llegar al final antes del límite de turnos.

La entrada consiste de casos de prueba , seguido por una línea que contiene sólo indicando el final de los casos de prueba.

La primera línea de un conjunto de datos contiene tres enteros separados por espacios N, S, T, donde

• N es el número total de casillas del tablero, 2 ≤n ≤200.

• S es el número máximo de plazas es posible avanzar en cada turno, 2 ≤S ≤10.

• T es el número máximo permitido de vueltas, donde N + 1 ≤ST y T ≤N + 1.

Luego continúan N una o más lineas con N enteros, que representan los números en el tablero. Cada número tiene una magnitud inferior a 10000.

Para cada conjunto de datos escriba en una línea el descuento máximo posible que se puede ganar al completar el juego.

Para completar el juego al que debe avanzar a un total de N + 1 en T turnos, cada uno a su vez avanzar de 1 a S casillas inclusive.