问题 F: 运动会

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:34 通过:12

题目描述

        小F和大F开了一所幼儿园,春天到了,幼儿园要举办一场运动会!
        幼儿园里有N个小朋友,运动会里有M个项目可供选择,每个小朋友都对M个项目有一定的喜好程度。对于第i个小朋友,他第j喜欢的项目是aij。并且保证对于每个小朋友,他都不会有两个一样喜欢的项目。
        幼儿园的园长小F和副园长大F对运动会的事情头疼不已,她们希望玩的人数最多的项目玩的人数最少,否则她们在最受欢迎的项目举行时会忙不过来。她们希望从M个项目中选出若干个项目在运动会中举行(可以全选,但不能一个也不选),每个小朋友会且仅会玩一个项目,并且他玩的项目一定是举行的项目中他最喜欢的。
        很不幸,今天幼儿园停电了,电脑不能用,小F和大F决定将这个问题交给聪明的你,请你求出玩的人数最多的项目玩的人数的最小值。

输入格式

第1行两个整数N和M,表示小朋友的个数和备选运动项目的个数。
第2至N+1行,每行M 个整数。第i+1行的第j个整数表示aij,表示第i个小朋友第j喜欢的项目。保证ai1..aiM是1..M的一个排列。

输出格式

一个整数,表示玩的人数最多的项目玩的人数的最小值。

输入样例 复制

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

输出样例 复制

2

数据范围与提示

【输出输出样例1】

sport.in

sport.out

4 5

5 1 3 4 2

2 5 3 1 4

2 3 1 4 5

2 5 4 3 1

2

【样例1解释】
一种最优方案是选择举行1,3,4 三个项目,这样的话,4个小朋友玩的项目分别是1,3,3,4,玩的人数最多的项目是3,有2个人玩,所以答案是2。
【输出输出样例2】

sport.in

sport.out

3 3

2 1 3

2 1 3

2 1 3

3

【样例2解释】
由于无论怎么选择举行的项目,3个小朋友玩的项目都是同一个,所以答案一定是3。
【数据范围】
对于30%的数据,M<=16。
对于另外30%的数据,N<=3。
对于100%的数据,1 <= N,M <= 300。