Problem
Eric trabalha como segurança na universidade, então depois de um dia de trabalho ele anda pelo prédio e apaga as luzes à noite.
O edifício tem n pisos e duas escadas à esquerda e à direita. Existem m quartos em cada andar ao longo do corredor que liga as escadas esquerda e direita. Em outras palavras, o edifício pode ser representado como um retângulo com n linhas e m + 2 colunas, onde a primeira e a última coluna — escadas e m colunas no meio — quartos.
Eric está agora parado no primeiro andar na escada da esquerda. Ele quer apagar as luzes de todos os lugares, mas não quer subir ao andar de cima antes de apagar todas as luzes do andar atual. Claro, Eric deve estar na sala para apagar as luzes. Eric gasta um minuto subindo as escadas de um andar ou indo para a próxima sala/escadas da próxima sala ou escadas no mesmo andar. Apagar as luzes da sala em que Eric está não toma seu tempo.
Ajude Eric a encontrar o tempo mínimo para desligar todas as luzes do prédio.
Observe que Eric não precisa retornar à sua posição original e também não é obrigado a visitar salas onde as luzes já estão apagadas.
Entrada:
A primeira linha contém dois inteiros n e m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — o número de andares e o número de quartos em cada andar, respectivamente.
As próximas n linhas contêm uma descrição do edifício. Cada linha contém uma sequência de zeros e uns de comprimento m + 2 descrevendo um andar (escadas à esquerda, depois m quartos, depois escadas à direita), onde 0 significa que as luzes estão apagadas e 1 significa que as luzes estão acesas. Os andares são dados de cima para baixo, em particular, a última linha descreve o primeiro andar.
O primeiro e o último caractere de cada linha descrevem escadas, então eles são sempre 0.
Saída:
Imprima um número — o tempo mínimo possível necessário para desligar todas as luzes.
Exemplos:
| Entrada |
Saída |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Explicações:
No primeiro exemplo, Eric irá primeiro para a sala 1 no primeiro andar e, em seguida, — para o quarto 2 no segundo andar usando qualquer escada.
No segundo exemplo, ele vai primeiro para a quarta sala no primeiro andar, sobe um andar na escada à direita, entra na quarta sala no segundo andar, sobe as escadas à direita novamente, vai para o segundo quarto no último andar.