Petit C joue à un jeu de déploiement de troupes. Dans ce jeu, il y a $n$ châteaux, et chaque partie oppose deux joueurs qui se disputent ces châteaux. Chaque joueur dispose de $m$ soldats et peut envoyer $a_i$ soldats au $i$-ème château pour tenter de le conquérir, de sorte que le nombre total de soldats ne dépasse pas $m$.

Si un joueur envoie un nombre de soldats strictement supérieur au double du nombre de soldats envoyés par son adversaire pour le $i$-ème château, ce joueur conquiert le château et obtient $i$ points.

Petit C va affronter $s$ autres joueurs un par un, et sa stratégie de déploiement doit être la même pour ces $s$ duels. Petit C a obtenu, par certains moyens, les stratégies que les $s$ autres joueurs vont utiliser, et il souhaite savoir quelle stratégie adopter pour maximiser son score total.

Comme la réponse n'est pas nécessairement unique, vous devez simplement afficher la valeur maximale du score total de Petit C.

Entrée

La première ligne de l'entrée contient trois entiers positifs $s, n, m$, représentant respectivement le nombre de joueurs autres que Petit C, le nombre de châteaux et le nombre de soldats dont dispose chaque joueur.

Les $s$ lignes suivantes contiennent chacune $n$ entiers non négatifs, représentant la stratégie d'un joueur, où le $i$-ème nombre $a_i$ est le nombre de soldats que ce joueur envoie au $i$-ème château.

Sortie

Affichez sur une seule ligne un entier non négatif représentant le score maximal que Petit C peut obtenir.

Exemples

Exemple 1

1 3 10
2 2 6

Sortie 1

3

Remarque 1

La stratégie optimale pour Petit C est d'envoyer $5$ soldats au $1$-er château et $5$ soldats au $2$-ème château.

Exemple 2

2 3 10
2 2 6
0 0 0

Sortie 2

8

Remarque 2

L'une des stratégies optimales pour Petit C est d'envoyer $2$ soldats au $1$-er château, $5$ soldats au $2$-ème château et $1$ soldat au $3$-ème château.

Sous-tâches

Pour $10\%$ des données, on garantit $s=1, n \le 3, m \le 10$.

Pour $20\%$ des données, on garantit $s=1, n \le 10, m \le 100$.

Pour $40\%$ des données, on garantit $n \le 10, m \le 100$.

Pour $20\%$ des données supplémentaires, on garantit $s=1$.

Pour $100\%$ des données, on garantit :

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2\times 10^4$
• Pour chaque joueur, $a_i \ge 0$ et $\sum\limits_{i=1}^n a_i \le m$.