Teognis, de curând la liceu, a început să capete puteri paranormale. Mai exact, el poate controla telepatic ţestoasa mascota a liceului, Percy. Patruns cumva in lumea mistică a ţestoaselor, el doreşte acum să captureze comoara magică a ţestoaselor.

Lumea testoaselor poate fi modelată ca o matrice cu N linii si M coloane, unde fiecare celula contine fie pământ fie apă. Atât lui Teognis cât si lui Percy le ia o unitate de timp sa se deplaseze dintr-o celula într-o altă celulă adiacentă ortogonal. Ei au voie sa se deplaseze simultan, dar si sa stea pe loc in timp ce celalalt se misca. Percy se poate afla doar pe apa, iar Teognis doar pe pamant. Comoara magica a testoaselor se aflta pe pamant. Pentru a putea trece peste apa, Teognis trebuie sa se urce pe Percy, care il poate duce peste apa. Care este timpul minim necesar pentru a castiga comoara ?

Lumea ţestoaselor poate fi modelată ca o matrice cu N linii si M coloane, unde fiecare celulă conţine fie pământ fie apă. Teognis şi Percy se deplasează după următoarele reguli:
 
- Atât lui Teognis cât si lui Percy le ia o unitate de timp să se deplaseze dintr-o celula într-o altă celulă adiacentă ortogonal (i.e, o celulă vecină pe una din cele patru direcţii cardinale).
- Ei au voie să se deplaseze simultan.
- Percy se va afla permanent pe celule cu apă.
- Teognis poate călători de unul singur doar pe celule cu pământ.
- Teognis poate călători pe apă dacă se află pe spatele lui Percy.
 
Comoara magică a ţestoaselor se află pe pământ. Care este timpul minim necesar pentru a castiga comoara ?

h2. Date de intrare

h2. Restricţii
* $1 ≤ N, M ≤ 1000$

* Pentru 15 de puncte se garanteaza ca N = 1
* Pentru alte 35 de puncte se garanteaza ca $1 ≤ N, M ≤ 50$

* Pentru *15* de puncte se garantează ca N = 1
* Pentru alte *35* de puncte se garantează ca $1 ≤ N, M ≤ 50$

h2. Exemplu