Excavación (2) P62226

Cuánto más profunda sea la mina, más mineral se podrá extraer, pero mayor resulta el coste de la excavación. Pero la situación es distinta a la del problema Excavación (1): el ayuntamiento donde está situada la mina te regala un vale con el que podrás excavar gratuitamente $V$ metros en cualesquiera de las $n$ explotaciones mineras de las que dispones, a repartir como más te convenga. Te pedimos que, conociendo el valor del mineral que se encuentra en los $k$ primeros metros de cada explotaciones mineras, digas como repartir esos $V$ metros de excavación gratuitos para obtener el máximo beneficio.

Entrada

Una entrada empieza con un número $N\ge 0$ en una línea, seguido de $N$ casos de prueba. Cada caso de pruebas empieza con una línea con los valores $k$, $n$ y $V$, seguido de $n$ líneas de $k$ valores cada una, donde el $j$-ésimo valor $a$ de la $i$-ésima línea indica el valor del mineral que se encuentra a $j$ metros de la superficie en la $i$-ésima explotación. Se te asegura que todos los valores $a$ cumplen $0\le a\le 1000$, y que $0<V\le nk$.

Salida

Para cada caso de pruebas, escribe en una línea el máximo beneficio que podrías obtener.

Puntuación

• Test1:   Entradas con $N<100$ casos donde $n$ es $1$ o $2$, y $k\le 10$.

• Test2:   Entradas con $N<100$ casos donde $n, k\le 5$.

• Test3:   Entradas con $N<100$ casos donde $n, k\le 40$.