Little C is playing a game of troop deployment. There are $n$ castles in the game, and each match is contested by two players. Each player has $m$ soldiers and can deploy $a_i$ soldiers to the $i$-th castle to compete for it, such that the total number of soldiers does not exceed $m$.
If a player deploys strictly more than twice the number of soldiers deployed by their opponent to the $i$-th castle, that player captures the castle and earns $i$ points.
Little C is about to play against $s$ other players, one by one. The deployment strategy must be the same for all $s$ matches. Little C has obtained the strategies that the other $s$ players will use and wants to know what strategy he should use to maximize his total score.
Since the answer may not be unique, you only need to output the maximum total score Little C can achieve.
Input
The first line contains three positive integers $s, n, m$, representing the number of other players, the number of castles, and the number of soldiers each player has, respectively.
The next $s$ lines each contain $n$ non-negative integers, representing a player's strategy, where the $i$-th number $a_i$ is the number of soldiers that player deploys to the $i$-th castle.
Output
Output a single non-negative integer representing the maximum total score Little C can obtain.
Examples
Input 1
1 3 10 2 2 6
Output 1
3
Note 1
Little C's optimal strategy is to deploy 5 soldiers to the 1st castle and 5 soldiers to the 2nd castle.
Input 2
2 3 10 2 2 6 0 0 0
Output 2
8
Note 2
One of Little C's optimal strategies is to deploy 2 soldiers to the 1st castle, 5 soldiers to the 2nd castle, and 1 soldier to the 3rd castle.
Subtasks
For $10\%$ of the data, $s=1, n \le 3, m \le 10$.
For $20\%$ of the data, $s=1, n \le 10, m \le 100$.
For $40\%$ of the data, $n \le 10, m \le 100$.
For another $20\%$ of the data, $s=1$.
For $100\%$ of the data:
- $1 \le s \le 100$
- $1 \le n \le 100$
- $1 \le m \le 2\times 10^4$
- For each player, $a_i \ge 0$ and $\sum\limits_{i=1}^n a_i \le m$.