该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例文件

题目描述

Hit point 是最近流行的一款游戏。

这是一个双人游戏，每场游戏分为 $N$ 关。

初始时，游戏双方每人将获得 $T$ 点的血量。

在每一关，双方各自向对方发动攻击，自己会消耗若干点数的血量。当然，如果自己的血量提前消耗完了，就无法再对对方发动攻击。而且，为了保留实力，也可以不向对方发动攻击，也就不消耗自己的血量。游戏结束时，不一定要把血量消耗完。

在第 $i$ 关，如果一方消耗的血量点数大于对方消耗的血量点数的 2 倍，则该方将获得该关的胜利，并得到 $i$ 的积分。失败的一方不获得积分。

现在有 $K$ 个人向小 A 发起挑战。小 A 要一一应战，进行 $K$ 场游戏。

通过某种秘密途径，小 A 已经提前预知了每个人的攻击策略，也就是他已经知道了每个人每一关会消耗多少血量。

小 A 非常懒。他希望设置自己的攻击策略，然后使用相同的策略去和所有人对决。

他该如何设置自己的攻击策略，可以使自己在 $K$ 场游戏中累积得到的总积分最多呢？

你能帮助他吗？你只需要输出他能够获得的最大总积分即可。

输入格式

第一行：三个正整数 $K, N, T$

接下来一个 $K×N$ 的矩阵 $A$，其中 $A_{i,j}$ 表示第 $i$ 个人在第 $j$ 关所消耗的血量点数。

输出格式

一个整数，表示答案。

样例 1 输入

1 3 9
1 2 3

样例 1 输出

3

样例 1 解释

第 1 关和第 2 关，小 A 设置自己消耗血量的点数分别为 3 和 5。这样他将获得前两关的胜利，总积分为 1+2=3 。

这只是一种可能的攻击策略。还有其他策略也可以使得小 A 得到 3 分。但不存在可以得到更多积分的策略。

样例 2 输入

2 3 9
1 2 3
0 1 0

样例 2 输出

9

样例解释

每场游戏分 3 关，小 A 设置自己消耗的点数依次为 3、 5、 1

与第 1 个人对决，总积分为 1 + 2 = 3

与第 2 个人对决，总积分为 1 + 2 + 3 = 6

最终总积分为 3 + 6 = 9

数据范围

• 对于 $10\%$ 的数据： $K = 1, N ≤ 3, T ≤ 10$
• 对于 $20\%$ 的数据： $K = 1, N ≤ 10, T ≤ 100$
• 对于 $40\%$ 的数据： $N ≤ 10, T ≤ 100$
• 对于另外 $20\%$ 的数据： $K = 1$
• 对于 $100\%$ 的数据： $1 ≤ K ≤ 100$, $1 ≤ N ≤ 100$, $1 ≤ T ≤ 20000$
• 对于第 $i$ 个人，满足 $A_{i,j} ≥ 0$，$\sum\limits_{j=1}^n A_{i,j} ≤ T$