配点 : 700 点
問題文
Mr.X 正在玩游戏,即将 征服 M 地下城。
每个地牢都是 N 由层次结构组成。地牢 i 可以得到第 j \ (1 \leq j \leq N) 等级制度有力量 有一只 A_{i,j} 怪兽。 Mr.X是一个地牢 按如下方式征服 x \ (1 \leq x \leq M) 。
- 地牢 x 进入时的初始健康状况 定义 h_x 。这里 必须满足 \displaystyle h_x > \max_{i=1}^{N} A_{x, i} 。
- 地牢 x 层次结构 输入 1 。 对于
- i = 1, 2, \cdots ,N ,层次结构如下:
征服 i 。你目前的体力 u 。
- u \leq A_{x, i} ,复活物品 1 次 将层次结构替换为 u 该值应乘以 h_x 变为。
- u 该值应乘以 u - A_{x, i} 继续 i + 1 。然而 当 i = N 时结束策略。
X先生的账户等级为 L 因此,在确定初始健康状况时 必须满足 \displaystyle \sum_{i=1}^{M} h_i \leq L 。另外, 在考虑每个 M 地下城中使用的复活物品数量时,我希望保持最大值尽可能小。在确定满足条件的初始生命值时,找到每个副本中使用的复活物品最大数量的最小值。
制約
- 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}
- 所有输入均为整数
配点
分数由以下子作业确定。
- (200 点) N \leq 3 \times 10^3
- (500 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。 (注:由于限制,输入量较大,要注意速度。)
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
3 3 24 5 2 3 9 3 7 3 7 1
出力例 1
2
h = (6, 10, 8) 然后地牢 1 有复活物品。 1 剩余的地下城里有复活物品。 2 需要一个,这是最佳的。
入力例 2
5 10 132 6 9 11 9 6 10 5 5 4 11 20 20 5 14 17 9 15 14 20 8 18 17 1 20 8 5 1 8 2 9 5 6 1 2 2 6 1 2 2 1 12 4 13 2 5 15 20 4 4 12
出力例 2
3