Cho bảng ký tự kích thước ~m * 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)), \forall i \leq m, j \leq 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 * 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 \leq 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à ~*~, trong đó ký tự ~*~ 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