Problem
Eric trabaja como guardia de seguridad en la universidad, así que después de un día de trabajo camina alrededor del edificio y apaga las luces por la noche.
El edificio tiene n plantas y dos escaleras a izquierda y derecha. Hay m habitaciones en cada piso a lo largo del corredor que conecta las escaleras izquierda y derecha. En otras palabras, el edificio se puede representar como un rectángulo con n filas y m + 2 columnas, donde la primera y la última columna — escaleras y m columnas en el medio — habitaciones.
Eric ahora está parado en el primer piso en las escaleras de la izquierda. Quiere apagar las luces de todas partes, mientras que no quiere subir al piso de arriba antes de apagar todas las luces del piso actual. Por supuesto, Eric debe estar en la habitación para apagar las luces. Eric pasa un minuto subiendo las escaleras de un piso o yendo a la siguiente habitación/escaleras desde la siguiente habitación o escaleras en el mismo piso. Apagar las luces de la habitación en la que está Eric no le quita tiempo.
Ayuda a Eric a encontrar el tiempo mínimo para apagar todas las luces del edificio.
Tenga en cuenta que Eric no tiene que volver a su posición original, y tampoco es necesario que visite las habitaciones donde las luces ya están apagadas.
Entrada:
La primera línea contiene dos enteros n y m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — el número de pisos y el número de habitaciones en cada piso, respectivamente.
Las siguientes n líneas contienen una descripción del edificio. Cada línea contiene una cadena de ceros y unos de longitud m + 2 que describen un piso (escaleras izquierda, luego m habitaciones, luego escaleras derecha), donde 0 significa que las luces están apagadas y 1 significa que las luces están encendidas. Los pisos se dan en orden de arriba a abajo, en particular, la última línea describe el primer piso.
El primer y último carácter de cada línea describen escaleras, por lo que siempre son 0.
Salida:
Imprimir un número — el tiempo mínimo posible requerido para apagar todas las luces.
Ejemplos:
| Entrada |
Salida |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Explicaciones:
En el primer ejemplo, Eric irá primero a la habitación 1 en el primer piso, y luego — a la habitación 2 en el segundo piso utilizando cualquier escalera.
En el segundo ejemplo, irá primero a la cuarta habitación del primer piso, subirá un piso por las escaleras de la derecha, entrará en la cuarta habitación del segundo piso, volverá a subir las escaleras de la derecha, irá al segundo habitación en el último piso.