T429164 「YAC Round 6」琪露诺的Homo馆攻坚战


琪露诺今天做了一个重大的决定，那就是向以蕾米莉亚为首的Homo馆宣战！ 咲夜最近不在家，于是Homo馆的女仆门老是往雾之湖中扔垃圾，所以琪露诺再也忍不住了。 琪露诺需要进行 $s$ 轮进攻。在Homo馆中，一共有 $n$ 座城堡。 **每一轮进攻中**，琪露诺有 $m$ 张冻符「Perfect Freeze」（后面简称符卡），琪露诺可以在进攻第 $i$ 座城堡时使用 $a_i$ 张符卡，即 $a_1, a_2, \ldots, a_n$。 Homo馆也采取了防御措施，琪露诺进行每一轮进攻时，每一座城堡都有一个镇守的小恶魔数量 $b_i$，即 $b_1, b_2, \ldots , b_n$。（但是Homo馆兵力有限，每一轮的 $\sum_{i=1}^n b_i$ 不会超过符卡数量 $m$。） **每一轮进攻时**，如果琪露诺在进攻第 $i$ 座城堡时使用的符卡数量 $a_i$ **严格大于** 城堡镇守的小恶魔数量 **$b_i$ 的两倍**，那么就可以获得 $i$ 个胜利点。 琪露诺进行 $s$ 轮进攻，但是 **$s$ 轮进攻所使用的符卡方案必须都相同**。 现在，琪露诺需要最大化自己的胜利点。 请你输出琪露诺可以得到的胜利点的 **最大值**。

第一行输入三个正整数 $s,n,m$，分别表示琪露诺进攻的轮数、Homo馆的城堡数 和 每一轮进攻拥有的符卡数量。 接下来 $s$ 行，每行 $n$ 个非负整数 $b_1, b_2, \ldots, b_n$，每一行表示这一轮进攻时，Homo馆采取的防守策略。其中第 $i$ 个数 $b_i$ 表示第 $i$ 座城堡镇守的小恶魔数量。

输出一行一个非负整数，表示琪露诺可以获得的胜利点的最大值。

#### 样例 1 解释 琪露诺的最佳符卡使用策略：进攻第 $1$ 座城堡和第 $2$ 座城堡时各使用 $5$ 张符卡，进攻第 $3$ 座城堡时使用 $0$ 张符卡。最终的总胜利点为 $1 \times 1 + 1 \times 2 = 3$ #### 样例 2 解释 琪露诺的最佳符卡使用策略（之一）：进攻第 $1$ 座城堡时使用 $3$ 张符卡，进攻第 $2$ 座城堡时使用 $5$ 张符卡，进攻第 $3$ 座城堡时使用 $1$ 张符卡。最终的总胜利点为 $1 \times 1 + 2 \times 2 + 1 \times 3 = 8$ #### 数据范围与约定 $1\le s \le 100$ ，$1\le n \le 100$ ，$1\le m \le 2 \times 10^4$ $b_i \ge 0$，$\sum\limits_{i=1}^n b_i \le m$