სუპერკენგურუ და რიცხვითი ლაბირინთი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია NxM ზომის ცხრილი. მის თითოეულ უჯრედში ჩაწერილია რიცხვი, რომელიც გვიჩვენებს, თუ რამდენით შეგიძლია გადასვლა ამ უჯრედიდან. გადასვლა ხორციელდება ორი მიმართულებიდან (მარჯვნივ,  ქვემოთ) ერთ–ერთით. თუკი უჯრედში უარყოფითი რიცხვი წერია, მასზე გადასვლა არ შეიძლება.

დაწერეთ პროგრამა, რომელიც დაადგენს, რა მინიმალური რაოდენობის სვლითაა შესაძლებელი მისვლა ცხრილის ზედა მარცხენა კუთხიდან ქვედა მარჯვენა კუთხეში.

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

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




მაგალითები

შესატანი მონაცემები
4 5 2 0 1 1 3 -4 2 2 -1 -9 3 2 -4 2 1 4 -6 2 1 9 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება