配点 : $700$ 点

問題文

高橋君は、スポーツ大会を開こうと考えています。 スポーツ大会に参加するのは、$1$ から $N$ までの番号のついた $N$ 人の人です。 また、大会で行うスポーツとして、$1$ から $M$ までの番号のついた $M$ 個のスポーツが候補に上がっています。 高橋君は、これらの中から $1$ つ以上（全てでもよい）のスポーツを選んで、スポーツ大会で実施します。

高橋君は、人 $i$ が、$j$ 番目に好きなスポーツが $A_{ij}$ であることを知っています。 それぞれの人は、スポーツ大会で実施されるスポーツのうち、自分が最も好きなスポーツだけに参加し、他のスポーツには参加しません。

高橋君は、一つのスポーツにたくさんの人が集まり過ぎることを懸念しています。 そこで高橋君は、スポーツ大会で実施するスポーツをうまく選んで、最も多くの人が参加しているスポーツの参加人数を最小化したくなりました。 最も多くの人が参加しているスポーツの参加人数の最小値を求めてください。

制約

• $1 \leq N \leq 300$
• $1 \leq M \leq 300$
• $A_{i1}$ , $A_{i2}$ , $...$ , $A_{iM}$ は、$1$ から $M$ の順列である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_{11}$ $A_{12}$ $...$ $A_{1M}$

$A_{21}$ $A_{22}$ $...$ $A_{2M}$

$:$

$A_{N1}$ $A_{N2}$ $...$ $A_{NM}$

出力

最も多くの人が参加しているスポーツの参加人数の最小値を出力せよ。

4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1

2

スポーツ $1$,$3$,$4$ を実施することにすると、人 $1$ はスポーツ $1$ に、人 $2$ はスポーツ $3$ に、 人 $3$ はスポーツ $3$ に、人 $4$ はスポーツ $4$ に参加します。 このとき、参加人数が最大のスポーツはスポーツ $3$ で、その参加人数 $2$ 人です。 また、参加人数が最大のスポーツの参加人数が $1$ 人になるような方法は存在しないので、この例の答えは $2$ になります。

3 3
2 1 3
2 1 3
2 1 3

3

全員の好みが一致しているので、どうやっても一つのスポーツに $3$ 人集まってしまいます。 よってこの例の答えは $3$ です。