Cho bảng ký tự kích thước \(m \times n\) chỉ gồm các ký tự 0, 1. Giá trị \(R(i)\) được tính bằng trị tuyệt đối của hiệu giữa số lượng ký tự 0 với ký tự 1 trên dòng \(i\), tương tự \(C(j)\) được tính bằng trị tuyệt đối của hiệu giữa số lượng ký tự 0 với ký tự 1 trên cột \(j\). Giá trị ổn định \(W = \max(\{R(i), C(j)\})\).

Ví dụ bảng ký tự sau có giá trị ổn định bằng \(2\):

0 1 0 1
1 0 1 0
0 1 1 0
0 0 0 1

Trong quá trình truyền dữ liệu, một số ô của bảng bị mất giá trị, người ta muốn khôi phục lại bảng để nhận được bảng có độ ổn định nhỏ nhất.

Yêu cầu: Cho bảng ký tự kích thước \(m \times n\) với một số ô bị mất, hãy khôi phục lại bảng để nhận được bảng có độ ổn định nhỏ nhất.

Input

• Dòng 1: chứa hai số nguyên \(m, n\) (\(m, n \le 100\)).
• \(m\) dòng sau, mỗi dòng một xâu độ dài \(n\) chỉ gồm các ký tự 0, 1 và *, trong đó ký tự * mô tả vị trí bị mất giá trị.

Output

• Gồm một dòng chứa một số \(W\) là độ ổn định nhỏ nhất của bảng khôi phục được.

Example

4 4
0101
1010
01**
****

0

Constraints

• \(m, n \le 100\).

Nguồn: 3D'21