Cho một bảng hình chữ nhật có \(N\) dòng và \(M\) cột gồm các chữ cái in thường từ a đến z. Bảng này có tính chất: ở mỗi cột, khi ghép các kí tự từ trên xuống dưới sẽ thu được một xâu đại diện và trong bảng các xâu đại diện là đôi một khác nhau.

Yêu cầu: hãy tìm cách xoá nhiều nhất các dòng (lần lượt từ dòng đầu tiên xuống dưới) của bảng để thu được một bảng mới vẫn đảm bảo tính chất trên. (Chỉ được xoá tối đa \(N - 1\) dòng)

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau một dấu cách.
• \(N\) dòng sau, mỗi dòng chứa một xâu có độ dài \(M\).

Output

• Ghi ra một số duy nhất là kết quả của bài toán.

Example

5 4
qwpt
abcf
bvoa
abka
bbhb

2

Scoring

• \(40\%\) số test tương ứng với số điểm có \(N, M \le 100\).
• \(30\%\) số test khác tương ứng với số điểm có \(N, M \le 500\).
• \(30\%\) số test còn lại tương ứng với số điểm có \(N, M \le 5000\).