12731273 SUSTech Online Judge
Problem 1273 --Diamond!

1273: Diamond!

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 14  Solved: 6
[Submit][Status][Web Board]

Description

Amayama is a collector of diamonds. Today he is invited to a party with his group.

For each participant in this party, he or she would receive a prize code which consists of m integers. For a group of participants, if all the people in this group have a continuous section of integers with length k in his or her prize code, and everyone in the group is able to convert own continuous section to any others' in the group by adding the same integer to every integer in own continuous section, then we call the group get a k-level diamond.

There are n people in Amayama's group and he wants to know which level of diamond can they get.

Input

The first line of input contains two integer n, m. (1<=n<=1000,1<=m<=100)

The following are n lines, and each line containing m integers standing the prize code that a member in Amayama's team gets.

Output

The output contains an integer k, which stands the level of diamond the group gets.

Sample Input

5 5
0 2 3 4 7
2 5 6 8 2
-9 -8 -6 1 2
100 101 102 100 103
5 6 7 0 2 

Sample Output

2

HINT

For the example, the continuous part for each prize code is:

2 3

5 6

-9 -8 (or 1 2)

100 101 (or 101 102)

5 6 (or 6 7)

[Submit][Status]