Harps and Tails

Interview

Time limit2sMemory limit512 MB

Summary

Flip any subset of columns of an H/T grid; find the maximum number of rows that can be made all-H.

Level: Medium4 of 10
Topics: Hash map, Greedy, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Gary likes the Celtic harp on the 1 euro coin. He has a grid of such coins with $n$ rows and $m$ columns. Each coin lies with either the harp or the tail facing up.

Gary wants as many rows as possible to show a harp in every cell. He is allowed one operation: choose a column and turn over every coin in that column. A coin that showed the harp then shows the tail, and a coin that showed the tail then shows the harp.

Gary may repeat the operation as many times as he likes. Find the largest number of rows that show a harp in every cell once he stops.

Input

The first line contains the number of rows $n$ and the number of columns $m$ , separated by a space ( $1 \le n, m \le 1000$ ).

Each of the next $n$ lines contains a string of length $m$ describing one row of the grid. The $j$ -th character of the $i$ -th line is 'T' if the coin in row $i$ , column $j$ shows a tail, and 'H' if it shows the harp.

Output

Print one line with the largest possible number of rows that show a harp in every cell.

Examples3

Example 1
Input
```
4 4
THTH
HTTT
HHHH
THTH
```
Expected output
```
2
```
Example 2
Input
```
3 5
TTTTT
TTTTT
TTTTT
```
Expected output
```
3
```

Example 3

Input

10 11
THHHTHTTHHH
THHHTHTTHHH
HTHTTHTTTHH
THHHTHTTHHH
TTTTHHTTTTH
THHHTHTTHHH
THHHTHTTHHH
TTTTHHTTTTH
HTHTTHTTTHH
THHHTHTTHHH

Expected output