Puzzle-bila

Se dă o matrice cu $N$ linii și $M$ coloane în care unele celule sunt libere și altele sunt blocate. Scopul nostru este să plecam din colțul stânga sus al matricei și să ajungem în colțul dreapta jos astfel încât să trecem doar prin celule libere și mergând doar în jos sau la dreapta la fiecare pas.
Pentru a putea ajunge până în colțul dreapta-jos al matricei avem voie să facem următoarea operație de oricâte ori: alegem o linie a matricei și o transpunem la stânga sau la dreapta cu o celulă. Celulele noi apărute prin acest proces vor fi automat blocate.

În următoarele imagini puteți vedea ce s-ar întâmpla dacă am aplica de $5$ ori operația de transpunere a primei linii la stânga:

În următoarele imagini puteți vedea ce s-ar întâmpla dacă am aplica de $5$ ori operația de transpunere a celei de-a treia linii la dreapta:

Cerință

Se cere să se calculeze numărul minim de operații prin care să se facă posibilă ajungerea din colțul stânga sus al matricei în colțul dreapta jos al matricei.

Date de intrare

Intrarea conține pe prima linie două numere naturale $N$ și $M$.
Următoarele $N$ linii vor conține fiecare câte un șir binar de lungime $M$, valorile de $1$ reprezentând celule blocate iar valorile de $0$ reprezentând celule libere.

Date de ieșire

Prima linie a ieșirii va conține un singur număr natural reprezentând numărul minim de operații necesar rezolvării problemei. Dacă ne este imposibil să ajungem din $(1, 1)$ în $(N, M)$ se va afișa $-1$.

Restricții și precizări

• $1 \leq N,M \leq 50 \ 000$.
• $1 \leq N \times M \leq 2 \ 000 \ 000$.

Exemplul

stdin

4 5
10100
00100
11001
00110

stdout

7

Explicație

Transpunem prima linie la stânga de $3$ ori.
Transpunem a doua linie la dreapta o dată.
Transpunem a patra linie la dreapta de $3$ ori.
În total avem $3+1+3=7$ operații.