Johnny has recently been getting into origami, but he finds traditional square pieces of paper boring. He recently ordered an interesting piece of origami paper whose shape can be described as a connected set of unit squares from an $$$h \times w$$$ grid. Two squares count as connected if they share a side — squares that only touch at a corner don't count. Additionally, the paper may have holes in it.
Johnny wants to make the outline of the paper as simple as possible. To do so, he may fold the paper at most once, using a fold which must go along a horizontal or vertical grid line. Everything on one side of the fold line is flipped over onto the other side, and the paper may stick out past the original grid after folding. Overlapping parts count as a single part of the visible shape.
A side is a maximal straight segment of the boundary with paper on the same side throughout the segment. Count both the outer boundary and the boundaries around holes. Segments that meet only at a corner with paper on opposite sides count separately.
For example, the following $$$3\times 3$$$ grid has $$$10$$$ sides before folding: $$$6$$$ around the outside and $$$4$$$ around the central gap.
###
#.#
.##
Can you help Johnny to fold the paper such that the resulting outline has the least number of sides?
The first line contains two integers $$$h$$$ and $$$w$$$ ($$$1 \le h,w \le 300$$$) — the height and width of the grid, respectively.
Each of the next $$$h$$$ lines contains a string of $$$w$$$ characters, each with either . or #. A # means the square is part of the paper, and a . means it isn't.
It is guaranteed that at least one square is # and that all # squares are connected through shared sides.
Output a single integer — the minimum number of sides of the visible shape after making at most one fold.
3 4##..###.####
4
3 5..#..#####..#..
8
5 7########..#..##..#..##..#..########
8
In the first sample test case, Johnny can fold the first two columns onto the remaining columns to get a rectangle with $$$4$$$ sides.
In the second sample test case, the paper initially has $$$12$$$ sides. Folding the first row onto the remaining rows gives a T shape with $$$8$$$ sides.
In the third sample test case, Johnny can fold the first three columns onto the remaining four to get a rectangular frame with one hole. The outer boundary has $$$4$$$ sides, and the boundary of the hole has $$$4$$$ sides. This gives $$$4+4=8$$$ sides in total.