← 返回题目列表

AtCoder · agc018_b

B. 体育节

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

高桥正在举办运动会。 有 N 将参加的人。这些人很容易被编号 1 通过 N。 另外,还有 M 本次比赛的运动选项。这些运动都有编号 1 通过 M。 在这些选项中,高桥将选择一项或多项运动(可能是全部)在比赛中进行。

高桥认识那个人 i的 j- 最喜欢的运动是运动 A_{ij}。 每个人只会参加赛事中实际进行的项目中自己最喜欢的项目,不会参加其他项目。

高桥担心其中一项运动会吸引太多人。 因此,他想仔细选择要进行的运动项目,以尽量减少参加人数最多的运动项目的参加人数。 找出参加人数最多的运动项目的最少可能参加人数。

约束

  • 1 \leq N \leq 300
  • 1 \leq M \leq 300
  • A_{i1} , A_{i2} , ... , A_{iM} 是以下整数的排列 1 to M.

输入

输入由标准输入按以下格式给出:

N M
A_{11} A_{12} ... A_{1M}
A_{21} A_{22} ... A_{2M}
:
A_{N1} A_{N2} ... A_{NM}

输出

打印参与人数最多的运动项目中可能的最小参与人数。


示例输入 1

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

示例输出 1

2

假设体育 选择要播放的 1, 3 和 4 。在这种情况下,人 1 将参加体育运动 1, 人 2 体育 3, 人 3 体育 3 和人 4 体育 4。 这里,参与人数最多的运动是Sport 3,有两名参与者。 没有办法减少参与人数最多的运动项目的参与人数 1。因此,答案是 2.


示例输入 2

3 3
2 1 3
2 1 3
2 1 3

示例输出 2

3

由于所有人对运动的品味都是相同的,所以无论选择什么运动,都会有一个三人参加的运动。 因此,答案是 3.