Maximum Row Deletions in a Letter Matrix

You are given a letter matrix of size (r \times c). Starting from the first row, you need to delete as many rows as possible such that after deletion, any two columns of the remaining matrix are different.

Two columns are considered equal if for every row in the remaining matrix, the letters in the two columns are the same. It is guaranteed that in the initial matrix, any two columns are different.

Formally, let the matrix be (A) with (r) rows and (c) columns. Suppose you delete the first (x) rows so that the remaining submatrix has rows (x+1, x+2, \ldots, r). For any two different columns (j) and (k), there should exist at least one row (i) (with (x+1 \le i \le r)) such that (A[i][j] \neq A[i][k]).

Your task is to determine the maximum number of rows (x) that can be deleted.

inputFormat

The first line of input contains two integers \(r\) and \(c\) denoting the number of rows and columns respectively.

Each of the following \(r\) lines contains a string of length \(c\), representing a row of the letter matrix.

outputFormat

Output a single integer representing the maximum number of rows that can be deleted while ensuring that any two columns in the remaining submatrix are different.

sample

3 3
abc
aaa
aca

0