問題文

ゆーてぃーさんは壁のタイルの張り替えをする予定です. ゆーてぃーさんには $N$ 個の希望パターンがあります.

$i$ 番目の希望パターンは $M$ 個の長さ $M$ の文字列で表され, 文字列 $S_{i,j}$ の $k$ 番目の文字が # のとき, 上から $j$ 行目, 左から $k$ 列目のマスは「黒マスでなければならない」, . のときは「黒マスでなくてもよい」ことを表します. なお, 各希望パターンは $90$ 度単位で回転させても構いません. ただし左右反転, 上下反転することはできません.

すべての希望パターンを満たすことのできる $M\times M$ のタイルのうち, 黒マスの数が最小となるものについて, 黒マスの数を求めてください.

制約

• $N, M$ は整数
• $1 \leq N \leq 8$
• $1 \leq M \leq 10$
• $S_{i,j}$ は # および . からなる長さ $M$ の文字列

入力

$N$ $M$
$S_{1, 1}$ 
$\vdots$
$S_{1, M}$ 
$\vdots$
$S_{N, 1}$ 
$\vdots$
$S_{N, M}$ 

出力

すべての希望パターンを満たす $M \times M$ のタイルに含まれる黒マスの数の最小値を求めてください.

最後に改行してください.

サンプル

3 4
####
....
....
....
....
.##. 
.##. 
....
....
....
....
...#

8

####  ....  ....
....  .##.  ....
....  .##.  ....
....  ....  ...#

####
.##.
.##.
....

2 5
#...#
#...#
#...#
#...#
.###.
#####
..#..
..#..
..#..
..#..

15

2 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

25