Grade Boost Operation

Time limit8sMemory limit512 MB

Summary

Reorder the N day sheets so that as many of the M subject columns as possible are non-decreasing, and report the maximum count (N up to 1000, M up to 40).

Level: Medium7 of 10
Topics: Graph, Bit manipulation, Brute force
Solved: No attempts yet

Problem

Taro attended a N-day study camp. Every day, M subjects were tested, and at the end of the camp, a report card listing all test scores was handed out. The report card has N sheets, and sheet i prints only the subject names and scores for day i (all M subjects).

Taro noticed that the report card had no dates. Before giving it to his mother, he changed it. He reordered the sheets, then numbered the pages from 1 onward and bound them into a booklet, creating a "fake report card". His goal is to maximize the number of subjects whose scores are weakly increasing with respect to the page number in the fake report card.

A score sequence is weakly increasing if for every 1 ≤ i < N, the score on page i+1 is greater than or equal to the score on page i.

Input

The input contains at most 50 datasets. Each dataset has the following format.

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

The first line contains N, the number of study days, and M, the number of subjects. N is an integer from 1 to 103, and M is an integer from 1 to 40.

The next N lines contain Taro's scores. Each line has M integers, where aij is Taro's score for subject j on day i. Each aij is an integer from 0 to 103.

The input ends with a line containing two zeros.

Output

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

Examples1

Example 1

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

Expected output