Cho bảng ký tự kích thước $m\ast 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)),\mathrm{\forall }i\le m,j\le n$.

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

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\ast 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 thứ nhất chứa hai số nguyên dương $m$ và $n$ ($m$, $n\le 100$).

$m$ dòng tiếp theo, mỗi dòng một xâu độ dài n chỉ gồm các ký tự $0$, $1$ và $\ast$, trong đó ký tự $\ast$ mô tả ô bị mất giá trị

Output:

In ra một số $W$ là độ ổn định của bảng khôi phục được.

Sample Input:

4 4
0101
1010
01**
****

Sample Output:

0

Giải thích test mẫu: Ta có thể điền bảng để tạo bảng như sau:

Như vậy, độ ổn định nhỏ nhất của bảng khôi phục được là $0$.

• Subtask 1: (10% số điểm): Dữ liệu đầu vào đảm bảo rằng số lượng ô bị mất không quá $20$.
• Subtask 2: (90% số điểm): Không có ràng buộc gì thêm.

  Đề HSG 12 vòng 2 tỉnh Bình Định, năm học 2023-2024