AT_pakencamp_2023_day2_d Many Dungeons

Mr.X 正在玩一个游戏，他需要挑战 $M$ 个地下城。 每个地下城有 $N$ 层。在第 $i$ 个地下城的第 $j\ (1 \leq j \leq N)$ 层里，有一个强度为 $A_{i,j}$ 的怪物。Mr.X 按照如下方式攻略第 $x\ (1 \leq x \leq M)$ 个地下城： 1. 首先，为进入第 $x$ 个地下城设定初始体力 $h_x$。这里必须满足 $h_x > \max_{i=1}^{N} A_{x, i}$。 2. 进入第 $x$ 个地下城的第 1 层。 3. 对于 $i=1,2,\cdots,N$，依次按照如下方式挑战第 $i$ 层。设当前体力为 $u$： 1. 如果 $u \leq A_{x,i}$，使用一次复活道具，并将 $u$ 恢复为 $h_x$。 2. 将 $u$ 替换为 $u - A_{x,i}$，进入第 $i+1$ 层。若 $i = N$ 则攻略完成。 Mr.X 的账号等级为 $L$，因此设定初始体力时需要满足 $\displaystyle \sum_{i=1}^{M} h_i \leq L$。另外，考虑 $M$ 个地下城分别所需的复活道具数量，以其中最大值尽量小为目标。请在满足条件的前提下，设定初始体力，求所有地下城中所需复活道具个数的最大值的最小值。

输入通过标准输入给出，格式如下。（注意：由于数据量较大，请注意程序的运行速度。） > $M$ $N$ $L$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,N}$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,N}$ $\vdots$ $A_{M,1}$ $A_{M,2}$ $\cdots$ $A_{M,N}$

请输出一行答案。在本题的限制下，可以证明一定存在一种初始体力的设定方法，使得 Mr.X 能够攻略所有地下城。

## 评分规则 评分分为如下小题： 1.（200 分）$N \leq 3 \times 10^3$ 2.（500 分）无额外限制。 ## 样例解释 1 若设 $h = (6, 10, 8)$，第 1 个地下城需要使用 1 个复活道具，剩下的两个地下城都需要 2 个复活道具，这是最优的方案。 ## 数据范围 - $1 \leq N \leq 3 \times 10^4$ - $1 \leq M \leq 10^2$ - $1 \leq A_{i,j} \leq 10^9$ - $\displaystyle \sum_{i=1}^{M} (\max_{j=1}^{N} A_{i,j} + 1) \leq L \leq 10^{18}$ - 输入均为整数。 由 ChatGPT 5 翻译