Great Strategy for Bring Up Grade

ID: 4196

Type: Default

8000ms

268MiB

Great performance strategy

Taro, an examinee, participated in an N-day study camp. In this training camp, M subjects are tested every day, and after the training camp, a report card with all the test scores is distributed. The report card consists of N sheets of paper, and on the i-th sheet, only the subject names and scores of the tests of all M subjects on the i-day are printed.

Taro noticed that the date was not written on the report card, and decided to add some work before giving the report card to his mother. By rearranging the order of the papers in the report card and writing the page numbers in order from the first sheet to make a booklet, a "fake report card" was created. Taro's purpose is to maximize the number of subjects whose test scores are monotonously increasing with respect to page numbers in the "False Report Card".

When Taro makes a "false grade report", find the maximum number of subjects whose test scores are monotonously increasing with respect to the page number.

However, the N-day test score is a broad monotonous increase with respect to the page number. For 1 ≤ i <N, the score on the i + 1 sheet is the score on the i-th sheet. It means that it is the above.

Input

The input consists of 50 or less datasets. Each dataset is represented in the following format.

N M a11 ... a1M ... aN1 ... aNM

The first line gives the number of days N and the number of subjects M for the study camp. N is an integer between 1 and 103, and M is an integer between 1 and 40.

Taro's score is given to the following N lines. Each line consists of M integers, where aij is the score of Taro-kun's subject j on day i, and aij is an integer between 0 and 103.

The end of the input is represented by a line of two zeros.

Output

For each dataset, output the maximum number of subjects whose test scores are monotonously increasing with respect to the page number on one line.

Sample Input

3 3 one two Three 2 1 3 3 3 3 8 5 3 3 4 3 4 2 1 2 3 2 7 9 7 8 7 3 4 3 3 4 1 2 2 3 2 4 5 6 5 6 7 9 7 7 8 4 5 5 6 6 5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 5 9 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 0 0

Output for the Sample Input

2 3 1 9

Example

Input

3 3 1 2 3 2 1 3 3 3 3 8 5 3 3 4 3 4 2 1 2 3 2 7 9 7 8 7 3 4 3 3 4 1 2 2 3 2 4 5 6 5 6 7 9 7 7 8 4 5 5 6 6 5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 5 9 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 0 0

Output

2 3 1 9

inputFormat

Input

The input consists of 50 or less datasets. Each dataset is represented in the following format.

N M a11 ... a1M ... aN1 ... aNM

The first line gives the number of days N and the number of subjects M for the study camp. N is an integer between 1 and 103, and M is an integer between 1 and 40.

Taro's score is given to the following N lines. Each line consists of M integers, where aij is the score of Taro-kun's subject j on day i, and aij is an integer between 0 and 103.

The end of the input is represented by a line of two zeros.

outputFormat

Output

For each dataset, output the maximum number of subjects whose test scores are monotonously increasing with respect to the page number on one line.

Sample Input

Output for the Sample Input

2 3 1 9

Example

Input

Output

2 3 1 9

样例

3 3
1 2 3
2 1 3
3 3 3
8 5
3 3 4 3 4
2 1 2 3 2
7 9 7 8 7
3 4 3 3 4
1 2 2 3 2
4 5 6 5 6
7 9 7 7 8
4 5 5 6 6
5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
5 9
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
0 0

</p>

#D5045. Great Strategy for Bring Up Grade

Great Strategy for Bring Up Grade