Flipping Coins 3

Interview

Time limit5sMemory limit512 MB

Summary

Flip whole rows or columns of an N by M grid of coins to leave as few tails as possible, with N at most 20.

Level: Medium6 of 10
Topics: Bit manipulation, Brute force, Greedy
Solved: No attempts yet

Problem

$N \times M$ coins lie on a table in $N$ rows and $M$ columns. Each coin shows either heads (H) or tails (T).

One operation flips all $M$ coins of a single row, or all $N$ coins of a single column. You may repeat the operation as many times as you want.

For example, suppose the coins start like this.

HHT
THH
THT

Flipping every coin in the first column gives this.

THT
HHH
HHT

Flipping every coin in the first row after that gives this.

HTH
HHH
HHT

Two coins show tails in the last state. Starting from the first state, no sequence of operations leaves fewer than two coins showing tails.

Given the starting state of the coins, you want to repeat the operation until as few coins as possible show tails. Write a program that finds that minimum count.

Input

The first line contains $N$ and $M$ , separated by a space. ( $1 \le N \le 20$ , $1 \le M \le 100{,}000$ )

Each of the next $N$ lines contains the starting state of one row. Each line is a string of length $M$ that lists the coins of that row from left to right, where H means heads and T means tails. There are no spaces between the characters.

Output

Print the minimum number of coins that can show tails.

Examples5

Example 1
Input
```
3 3
HHT
THH
THT
```
Expected output
```
2
```
Example 2
Input
```
3 4
HTTH
THTH
HTTT
```
Expected output
```
2
```
Example 3
Input
```
1 6
TTHTHT
```
Expected output
```
0
```
Example 4
Input
```
2 5
HHHHH
HHHHH
```
Expected output
```
0
```
Example 5
Input
```
4 4
TTTT
TTTT
TTTT
TTTT
```
Expected output
```
0
```