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 celulă într-o altă celulă adiacentă ortogonal (i.e, o celulă vecină pe una din cele patru direcţii cardinale).

- 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ă undeva pe pământ. Care este timpul minim necesar pentru ca Teognis să ajungă la celula în care se află comoara?

Comoara magică a ţestoaselor se află pe pământ. Care este timpul minim necesar pentru a castiga comoara ?

h2. Date de intrare

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

* Celulele în care se află Teognis, respectiv comoara iniţial conţin pământ.
* Celula în care se află iniţial Percy conţine apă.

h2. Exemplu