Tədqiqatçılar

Kosmik ekspedisiya Marsa göndərildi və orada həyat formaları tapıldı. Ukraynalı kosmonavt-tədqiqatçılar Yehor Kulvasenko və Petro Kamrabov, adi yer siçanlarına bənzəyən kiçik varlıqlar aşkar etdilər.

Planetin səthinə bir çıxışdan sonra planetar stansiyaya qayıdarkən kosmonavtlar heyrətamiz bir mənzərə müşahidə etdilər: marslı "siçanlar" çox minilliklər əvvəl (araşdırmalar göstərdi ki) naməlum bir qüvvə tərəfindən kvadrat hüceyrələrə bölünmüş düzbucaqlı bir platoda qruplara toplaşmışdılar.

Platounun koordinatlarını bort kompüterinə ötürdükdən sonra alimlər onun xəritəsini aldılar. Xəritədə hər bir hüceyrədə neçə marslı "siçan" olduğu və hansı hüceyrələrin keçilməz (ölümcül radiasiya səviyyəsinə malik) olduğu göstərilmişdi.

Alimlər xəritədə sağ yuxarı küncdə yerləşirdilər.

Tədqiqatçılar dərhal anladılar ki, oksigen ehtiyatları məhduddur, buna görə də platoda yalnız stansiyaya doğru: sola və ya aşağıya hərəkət edə bilərlər. Onlar platonun sağ yuxarı küncündən sol aşağı küncünə qədər keçərək ən çox marslı siçanları tutmağa qərar verdilər, lakin yüksək radiasiya səviyyəsi olan hüceyrələrə addım atmadan. Tədqiqatçılara optimal yolu tapmaqda kömək edin.

Giriş məlumatları

Faylın ilk sətiri platounun ölçülərini M və N göstərir, bunlar 150-dən çox deyil. Növbəti M sətirində N tam ədəd platonun təsvirini ehtiva edir. Əgər ədəd qeyri-mənfi olarsa, bu, həmin hüceyrədəki siçanların sayını göstərir. Əgər ədəd -1 olarsa, bu hüceyrə keçilməz sayılır. Bütün ədədlər 10^5-dən çox deyil.

Çıxış məlumatları

Tədqiqatçıların tuta biləcəyi maksimum siçan sayını müəyyən edin və onu çıxış faylının yeganə sətirində yazın.