동전 뒤집기 3

$N \times M$개의 동전이 $N$행 $M$열을 이루어 탁자 위에 놓여 있다. 각 동전은 앞면(H)이 위를 향하도록 놓여 있거나 뒷면(T)이 위를 향하도록 놓여 있다.

한 번의 작업으로 한 행에 놓인 $M$개의 동전을 모두 뒤집거나, 한 열에 놓인 $N$개의 동전을 모두 뒤집을 수 있다. 이 작업은 원하는 만큼 반복할 수 있다.

예를 들어 처음 상태가 다음과 같다고 하자.

HHT
THH
THT

첫 번째 열의 동전을 모두 뒤집으면 아래와 같이 된다.

THT
HHH
HHT

이어서 첫 번째 행의 동전을 모두 뒤집으면 아래와 같이 된다.

HTH
HHH
HHT

마지막 상태에서 뒷면이 위를 향한 동전은 두 개이다. 처음 상태에서 작업을 아무리 반복해도 뒷면이 위를 향한 동전을 두 개보다 적게 만들 수는 없다.

동전의 처음 상태가 주어질 때, 작업을 반복해 뒷면이 위를 향한 동전의 개수를 최소로 만들려고 한다. 그 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다. ($1 \le N \le 20$, $1 \le M \le 100{,}000$)

둘째 줄부터 $N$개의 줄에 걸쳐 동전의 처음 상태가 주어진다. 각 줄은 길이가 $M$인 문자열이고, 한 행에 놓인 동전의 상태를 왼쪽부터 차례대로 나타낸다. 앞면이 위를 향하면 H, 뒷면이 위를 향하면 T이며 문자 사이에 공백은 없다.

첫째 줄에 뒷면이 위를 향한 동전의 최소 개수를 출력한다.