D - Many Dungeons Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

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 を定める。ここで \displaystyle 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} の場合、復活アイテムを 1 回用いて 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 個のダンジョンそれぞれで使う復活アイテムの個数を考えたとき、その最大値をできるだけ小さくしたい。条件を満たすように初期体力を決める時、各ダンジョンで使う復活アイテムの個数の最大値の最小値を求めよ。

制約

  • 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}
  • 入力は全て整数

配点

以下の小課題に点数が定められている。

  1. (200 点) N \leq 3 \times 10^3
  2. (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