მოცემულია 0-ებისა და 1-ებისაგან შედგენილი მართკუთხა არე. იპოვეთ ზედა მარცხენა კუთხიდან ქვედა მარჯვენა კუთხემდე უმოკლესი გზა, რომელიც მხოლოდ ერთიანებისაგან შედგება. მოძრაობა შეიძლება მხოლოდ ზემოთ, ქვემოთ, მარცხნივ და მარჯვნივ (დიაგონალზე გადასვლა არ შეიძლება). საწყისი წერტილი უმოკლეს გზაში არ ჩათვალოთ.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი N და M (1<N,M<=20) - მართკუთხა არის ზომები.

გამოსატანი მონაცემები: ერთი მთელი რიცხვი - უმოკლესი მანძილის სიგრძე. თუ გზა ზედა მარცხენა კუთხიდან ქვედა მარჯვენა კუთხემდე არ არსებობს, გამოიტანეთ -1.

მაგალითები

შესატანი მონაცემები
5 5
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
                  დაკოპირება

გამოსატანი მონაცემები
16
                  დაკოპირება