2020 South Central USA Regional Contest

Start

2021-03-06 10:00 AKST

2020 South Central USA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -103 days 19:27:04

Time elapsed

5:00:00

Time remaining

0:00:00

Problem F
Exam Manipulation

A group of students is taking a True/False exam. Each question is worth one point. You, as their teacher, want to make your students look as good as possible—so you cheat! (I know, you would never actually do that.) To cheat, you manipulate the answer key so that the lowest score in the class is as high as possible.

What is the best possible lowest score you can achieve?

Input

The first line of input contains two integers $n$ ($1 \le n \le 1\, 000$) and $k$ ($1 \le k \le 10$), where $n$ is the number of students, and $k$ is the number of True/False questions on the exam.

Each of the next $n$ lines contains a string of length $k$, consisting only of upper-case ‘T’ and upper-case ‘F’. This string represents the answers that a student submitted, in the order the questions were given.

Output

Output, on a single line, the best possible lowest score in the class.

Sample Input 1 Sample Output 1
5 4
TFTF
TFFF
TFTT
TFFT
TFTF
2
Sample Input 2 Sample Output 2
3 5
TFTFT
TFTFT
TFTFT
5