¡La competencia comenzará pronto, incluso aunque los concursantes no tienen idea de que trata! Las sillas se han dispuesto para formar un rectángulo que contiene ~R~ filas (numeradas del ~1~ al ~R~) \(× C\) columnas (numeradas del ~1~ al ~C~) dentro de la sala del concurso. Cada silla puede estar vacía u ocupada por un concursante.

La condición de todas las sillas en la sala de concurso en este punto se puede representar mediante una matriz ~S~. Si la silla en la ~i~-ésima fila y la ~j~-ésima columna están vacías en este punto, entonces ~S [i] [j]~ contiene un carácter ~0~. De lo contrario, si la silla en la ~i~-ésima fila y la ~j~-ésima columna está ocupada por un concursante en este punto, entonces ~S [i] [j]~ contiene un carácter ~1~.

Sheldon como de costumbre quiere ordenar. Al observar los asientos distribuidos de los concursantes, los reunirá primero antes de la sesión informativa. Él quiere que todos los concursantes estén reunidos en un rectángulo. En otras palabras, que todos los concursantes se sienten entre la fila ~r_1~-ésima a la ~r_2~-ésima y la columna ~c_1~-ésima a ~c_2~-ésima (para algún valor ~1 \le r_1 \le r_2 \le R~ y ~1 \le c_1 \le c_2 \le C~), y allí no haya una silla vacía dentro de los rangos de filas y columnas mencionados.

Para reunir a los concursantes, Sheldon podría tener que trasladar a algunos de los concursantes a cualquier asiento vacío. Él quiere mover a la menor cantidad de concursantes posible, ya que cada movimiento molesta a otros concursantes. Él se pregunta sobre el número mínimo de movimientos que deben realizarse para que todos los concursantes estén reunidos en un rectángulo, o si es imposible hacerlo, en realidad él ya lo sabe, pero quiere preguntárselo a usted para realizar un experimento.

Formato de entrada

La entrada se da con el siguiente formato:

R C
S [1] [1] S [1] [2] ... S [1] [C]
S [2] [1] S [2] [2] ... S [2] [C]
. . .
. . .
. ..
S [R] [1] S [R] [2] ... S [R] [C]

Formato de salida

Una sola línea que contenga el número mínimo de movimientos que deben realizarse para que todos los concursantes queden agrupados en un rectángulo, o -1 si es imposible hacerlo.

Restricciones

• ~1 \le R, C~.

• \(1 \le R × C \le 100.000\).

• ~S~ contiene solo los caracteres ~0~ o ~1~.

• Hay al menos un carácter ~1~ en ~S~.

Subtareas

Subtarea 1 (18 puntos)

• ~R = 1~.

• \(R × C \le 2,000\).

Subtarea 2 (8 puntos)

• ~R = 1~.

Subtarea 3 (28 puntos)

• \(R × C \le 200\).

Subtarea 4 (19 puntos)

• \(R × C \le 2,000\).

Subtarea 5 (27 puntos)

• Sin restricciones adicionales

Ejemplos

Entrada de muestra 1

4 3
000
110
110
000

Salida de muestra 1

0

Explicación de la muestra 1

En esta muestra, todos los concursantes se han reunido en un rectángulo, por lo que no es necesario realizar ningún movimiento.

Entrada de muestra 2

3 4
0010
1100
0100

Salida de muestra 2

1

Explicación de la muestra 2

En esta muestra, se puede mover al concursante sentado en la primera fila y la tercera columna al asiento en la tercera fila y la primera columna. Después del movimiento, todos los concursantes se han reunido en un rectángulo, por lo que solo se debe realizar 1 movimiento.

Entrada de muestra 3

3 3
111
101
111

Salida de muestra 3

-1

Explicación de la muestra 3

En esta muestra, no hay forma de reunir a todos los concursantes en un rectángulo.