Description

You are given an $r \times c$ matrix of letters. Starting from the first row of this matrix, you need to delete as many rows as possible, while ensuring that no two columns in the matrix are identical. Output the maximum number of rows that can be deleted.

• Two columns are considered identical if, for every row, the letters in these two columns are the same.
• In the initial matrix, any two columns are different.

Input Format

The first line contains two integers $r, c$.

The next $r$ lines each contain $c$ letters, describing the letter matrix.

It is guaranteed that all letters in the matrix are lowercase letters.

Output Format

Output one integer on one line, representing the maximum number of rows that can be deleted.

2 6
dobarz
adatak

0

3 4
alfa
beta
zeta

2

4 6
mrvica
mrvica
marica
mateja

1

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \le r, c \le 1000$.

Notes

This problem is translated from COCI2010-2011 CONTEST #3 T4 ZNANSTVENIK。

Translated by ChatGPT 5