• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

A histogram is a simple rectilinear polygon \(H\) (i.e. the interior angle at each vertex is either \(90\)° or \(270\)°) that has a horizontal edge seeing every point \(q\) inside (i.e. the interior or the boundary of) \(H\). Here, we say that an edge sees a point \(q \in H\) if there is a vertical segment \(s\) connecting \(e\) to \(q\) that is lying inside \(H\).

Let \(H\) be a histogram with \(n\) vertices, and consider a decomposition \(R\) of \(H\) into rectangles whose sides are vertical or horizontal. The vertices of the rectangles need not all be vertices of \(H\): it is allowed to introduce additional vertices, on the boundary of \(H\) and/or in its interior. The stabbing number of a horizontal or vertical segment \(s\) inside \(H\) with respect to such a decomposition \(R\) is the number of rectangles from \(R\) whose interior (not just their boundaries) are intersected by \(s\). The stabbing number of \(R\) is the maximum stabbing number of any horizontal or vertical segment \(s\) that lies inside \(H\). The goal is to compute a decomposition \(R\) with the minimum stabbing number.

ورودی

The first line of the input contains two positive integers \(m\) and \(n\) (\(1 \leq m,n \leq 50\)) denoting the number of rows and the number of columns of the table illustrating the histogram, respectively. The next \(m\) lines, each contains exactly n characters. *s denote the boundary of the histogram. The rest is filled with dots (.). Each edge of the histogram contains at least three *s. You can assume the given histogram has at least four and at most 16 edges, and edges do not overlap, intersect or touch each other; i.e. each * is adjacent to exactly two other * characters.

خروجی

Print the stabbing number of the given histogram in one line.

مثال‌ها

ورودی نمونه ۱

10 13
.....****....
.....*..*....
.....*..***..
.....*....*..
.....*....***
...***......*
...*........*
****........*
*...........*
*************

خروجی نمونه ۱

2

ورودی نمونه ۲

8 15
...............
.........*****.
....***..*...*.
....*.*..*...*.
.****.****...*.
.*...........*.
.*************.
...............

خروجی نمونه ۲

2