Takahashi is hosting an sports meet. There are N people who will participate. These people are conveniently numbered 1 through N. Also, there are M options of sports for this event. These sports are numbered 1 through M. Among these options, Takahashi will select one or more sports (possibly all) to be played in the event.

Takahashi knows that Person i's j-th favorite sport is Sport A_{ij}. Each person will only participate in his/her most favorite sport among the ones that are actually played in the event, and will not participate in the other sports.

Takahashi is worried that one of the sports will attract too many people. Therefore, he would like to carefully select sports to be played so that the number of the participants in the sport with the largest number of participants is minimized. Find the minimum possible number of the participants in the sport with the largest number of participants.

Constraints

* 1 \leq N \leq 300
* 1 \leq M \leq 300
* A_{i1} , A_{i2} , ... , A_{iM} is a permutation of the integers from 1 to M.

Input

Input is given from Standard Input in the following format:


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


Output

Print the minimum possible number of the participants in the sport with the largest number of participants.

Examples

Input

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


Output

2


Input

3 3
2 1 3
2 1 3
2 1 3


Output

3
# 写経AC
from collections import deque, defaultdict

N,M = map(int, input().split())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

def check(X):
    """
    最多参加のスポーツの参加人数がX以下になるか
    """
    # que[i]: 人iが参加したいスポーツ
    que = [deque() for _ in range(N)]
    # ng[j]: スポーツjはダメ
    ng = [False] * M
    for i in range(N):
        for j in range(M):
            que[i].append(A[i][j])
    
    while True:
        # cnt[j]: スポーツjに参加したい人数
        cnt = defaultdict(int)
        for i in range(N):
            cnt[que[i][0]] += 1

        # 定員over フラグ
        flag = False
        for s, c in cnt.items():
            if X < c:
                flag = True
                ng[s] = True

        # 参加人数が全てX以下
        if not flag:
            return True
        
        for i in range(N):
            # 参加したいスポーツがngの場合
            while que[i] and ng[que[i][0]]:
                que[i].popleft()
            # 参加できるスポーツがない場合
            if not que[i]:
                return False

def main():
    ng, ok = 0, N
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()