Ma trận tốt

Một ma trận nhị phân (mỗi ô là $0$ hoặc $1$) được gọi là tốt nếu mọi ma trận con vuông có cạnh chẵn đều chứa một số lẻ các số $1$.

Ở đây, một ma trận con vuông cạnh chẵn là một ma trận con vuông kích thước $k\times k$ với $k$ chẵn (tức $k\in \{2,4,6,\dots \}$).

Cho một ma trận nhị phân $a$ gồm $n$ dòng và $m$ cột. Hãy xác định số ô ít nhất cần thay đổi (đổi $0$ thành $1$ hoặc ngược lại) để ma trận trở thành tốt, hoặc cho biết không thể làm được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số dòng và số cột của ma trận.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự $0$ hoặc $1$ mô tả ma trận $a$.

Dữ liệu ra

• In ra số ô ít nhất cần thay đổi để ma trận trở thành tốt, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le m\le {10}^6$ và $n·m\le {10}^6$.

Ví dụ