El pequeño C está jugando a un juego de despliegue de tropas. En el juego hay $n$ castillos, y cada partida es disputada por dos jugadores. Cada jugador tiene $m$ soldados y puede enviar $a_i$ soldados al $i$-ésimo castillo para intentar capturarlo, de modo que el número total de soldados no exceda $m$.

Si un jugador envía a un castillo $i$ un número de soldados estrictamente mayor al doble de los soldados enviados por su oponente, dicho jugador captura el castillo y obtiene $i$ puntos.

Ahora, el pequeño C se enfrentará a otros $s$ jugadores en partidas uno a uno, y debe utilizar la misma estrategia de despliegue de soldados para todas estas $s$ partidas. El pequeño C ha obtenido información sobre las estrategias que utilizarán los otros $s$ jugadores y quiere saber qué estrategia debe emplear para maximizar su puntuación total.

Dado que la respuesta podría no ser única, solo necesitas imprimir el valor máximo de la puntuación total del pequeño C.

Entrada

La primera línea de la entrada contiene tres enteros positivos $s, n, m$, que representan el número de otros jugadores, el número de castillos y el número de soldados que tiene cada jugador, respectivamente.

Las siguientes $s$ líneas contienen, cada una, $n$ enteros no negativos que representan la estrategia de un jugador, donde el $i$-ésimo número $a_i$ indica el número de soldados que ese jugador envía al $i$-ésimo castillo.

Salida

Imprime una sola línea con un entero no negativo que represente la puntuación máxima que puede obtener el pequeño C.

Ejemplos

Ejemplo 1

1 3 10
2 2 6

Salida 1

3

Nota 1

La mejor estrategia del pequeño C es enviar $5$ soldados al primer castillo y $5$ soldados al segundo castillo.

Ejemplo 2

2 3 10
2 2 6
0 0 0

Salida 2

8

Nota 2

Una de las mejores estrategias del pequeño C es enviar $2$ soldados al primer castillo, $5$ soldados al segundo castillo y $1$ soldado al tercer castillo.

Subtareas

Para el $10\%$ de los datos, se garantiza que $s=1, n \le 3, m \le 10$.

Para el $20\%$ de los datos, se garantiza que $s=1, n \le 10, m \le 100$.

Para el $40\%$ de los datos, se garantiza que $n \le 10, m \le 100$.

Para otro $20\%$ de los datos, se garantiza que $s=1$.

Para el $100\%$ de los datos, se garantiza que:

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2\times 10^4$
• Para cada jugador, $a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$.