Problem Description

Given an $r \times c$ matrix of letters, you need to start from the first row of the matrix and delete as many rows as possible, 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 the letters in the same row of these two columns are equal.
• Initially, any two columns in the matrix are not identical.

Input Format

The first line of input contains two integers $r$ and $c$.

The next $r$ lines, each containing $c$ letters, describe the letter matrix.

The letters in the matrix are all lowercase.

Output Format

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

Sample Input and Output

Sample Input #1

2 6
dobarz
adatak

Sample Output #1

0

Sample Input #2

3 4
alfa
beta
zeta

Sample Output #2

2

Sample Input #3

4 6
mrvica
mrvica
marica
mateja

Sample Output #3

1

Notes

Data Size and Constraints

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

Notes

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

见题面 Input 部分

见题面 Output 部分