F - We wanna win the trick taking
Benihuki
2
s
1024
MB
400
点
問題文
$N$人のプレイヤーでゲームをします。各プレイヤーにはカードが$M$枚ずつ配られます。$i$人目に配られる$j$枚目のカードには $A_{i, j}$の整数が書かれています。どの2枚のカードについても、値は異なります。
ゲームは$M$ラウンドで構成され、各ラウンドでは以下の操作を順に行います。
- 各プレイヤーは持っているカードの中から一様ランダムにカードを1枚選び、場に出す
- 場に出された$N$枚のカードの中で、一番大きな数値のカードを出したプレイヤーが1点得る
- そのラウンドで出されたカードをすべて焼却する。焼却したカードは以後場に出せない
$M$ラウンド終了時点で、$K$点以上得点している可能性のあるプレイヤーの人数を出力してください。
制約
- $1 \le N, M$
- $1 \le NM \le 3 \times 10^5$
- $1 \le K \le M$
- $1 \le A_{i, j} \le 10^9$
- $i \neq k$または$j \neq l$ならば、$A_{i, j} \neq A_{k, l}$
入力
$N$ $M$ $K$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, M}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, M}$
$\vdots$
$A_{N, 1}$ $A_{N, 2}$ $\ldots$ $A_{N, M}$
出力
答えを1行に出力してください。末尾に改行を加えてください。
入力例 1
3 3 2
7 5 3
4 10 6
1 2 8
出力例 1
2
例えば
- 1人目が7、2人目が6、3人目が1を出して1人目が勝つ
- 1人目が5、2人目が4、3人目が2を出して1人目が勝つ
- 1人目が3、2人目が10、3人目が8を出して2人目が勝つ
とゲームが進行したとき、1人目のプレイヤーは2点を得られ、したがって2点以上得られるプレイヤーのひとりとなります。
入力例 2
4 2 2
4 5
3 6
2 7
1 8
出力例 2
0
どのようにゲームが進行しても、いずれのプレイヤーも2点以上得点できることはありません。
入力例 3
1 5 5
1 2 3 4 5
出力例 3
1