Ibrahim's dissertation

Ibrahim is finishing his studies this year and is exploring the longest common subsequence for a small part of his dissertation. In his research, he needed to find the longest common subsequence of permutations. Ibrahim is not good at permutations. Help him with this.

You are given the number of permutations $k$. Each permutation is a sequence of numbers $1,2,...,n$ in arbitrary order. Find the length of the longest common subsequence of the given permutations.

Note 1. A sequence of numbers $1,2,...,n$ written in arbitrary order is called a permutation of $n$ elements.

Note 2. A subsequence of a sequence is a sequence that can be obtained from the given sequence by removing some elements without changing the order of the remaining elements or without removing any elements. A subsequence that belongs to two or more sequences is called a common subsequence of these sequences.

Input

The first line contains two integers $n(1\le n\le 1000)$ and $k(2\le k\le 5)$. Each of the next $k$ lines contains a permutation consisting of $n$ integers $1,2,...,n$.

Output

Print the length of the longest common subsequence of the given permutations.

Examples

In the first example, the sequence $235$ or $245$ is the longest common subsequence. They both appear in both permutations.

In the second example, $123$ is the longest common subsequence. It appears in all three permutations.