This page is still under construction.

Parts of this page are still being built. What you see may change.

Harmonious Matrix

Time limit5sMemory limit768 MB

Summary
Given a 2xN or 3xN matrix of distinct integers, find the largest subset of columns whose orderings within each row are identical, and report its column count.
Level

Hard8 of 10

Topics
Sorting, Hash map, Prefix sum, Greedy
Solved
No attempts yet

Problem

Consider a 2×N or 3×N matrix (two-dimensional array) made up of distinct positive integers. Given a matrix Q, a matrix formed by choosing one or more columns and joining them in order is called a column-submatrix of Q. (Q is also a column-submatrix of itself.)

For example, let Q be the following matrix.

The following matrix X is the column-submatrix formed by choosing columns 2, 3, 5, 6, and 8 of Q.

Define the rank matrix RX of matrix X as follows. The entry RX[i, j] in row i, column j of RX gives the rank of the entry X[i, j] in row i, column j of X within row i of X (the largest number has rank 1). The rank matrix RX of X is as follows. (All entries of the original matrix Q are distinct, so no two entries in a row of RX share a rank.)

The 74 stored at X[1,1] is the second largest among the entries 74, 41, 89, 52, 63 of row 1 of X, so 2 is stored at RX[1, 1]. The other entries are computed the same way.

If all rows of the rank matrix of a column-submatrix agree, that column-submatrix is called harmonious. For RX, rows 1 and 3 agree, but row 2 agrees with no other row, so it is not a harmonious matrix.

The following are the column-submatrix Y formed by choosing columns 2, 3, 6, and 8 of Q, and its rank matrix RY.

All rows of the rank matrix RY agree, so the column-submatrix Y is harmonious. The largest harmonious column-submatrix of Q has size 3×4.

Given a 2×N or 3×N matrix Q, write a program that finds the number of columns of the largest harmonious column-submatrix of Q.

Input

The first line of standard input contains the number of rows M and the number of columns N. The next M lines give the rows, one row per line. Each line contains N positive integers, the entries of one row in column order, separated by spaces.

Output

Print to standard output a single integer, the number of columns of the largest harmonious column-submatrix.

Constraints

In every subtask, each entry of the matrix is between 1 and 109 inclusive.

Examples2

  1. Example 1

    Input
    3 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
29 49 13 26 59 17 62 34 19
    Expected output
    4

  2. Example 2

    Input
    2 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
    Expected output
    5