Мutantlar-2#3739
İncəsənət, Mutantlar və İnformasiya Texnologiyaları İnstitutunda şirin rəngarəng heyvanlar yetişdirilir. Lakin qəfildən heyvanlardan biri İnstitutdan çıxış yolunu tapdı və qaçdı. Tale elə gətirdi ki, o, Möcüzəvi Mutantşəhərə düşdü. İnanmayacaqsınız, şəhər küçələrə bölünüb, küçələrin kəsişməsində isə kəsişmələr yerləşir.
Mutantşəhərin qəribəliyi ondadır ki, kəsişmədən kəsişməyə yalnız şərqə və ya cənuba getmək olar, həmçinin hər kəsişmədə cərimə alınır. Mutantımız şəhərin xəritəsini tapdı, bu xəritə N x M ölçülü bir şəbəkə şəklindədir, burada i-ci sıranın və j-ci sütunun kəsişməsində bu kəsişməyə düşərkən alınacaq cərimənin ölçüsü göstərilib.
Heyvan şəhərin şimal-qərb küncündə yerləşir. Ona Mutantşəhərin cənub-şərq küncünə minimal mümkün cərimə ödəməklə çatmağa kömək edin.
Giriş faylının birinci sətirində iki təbii ədəd N və M (1 ≤ N, M ≤ 1000) verilir.
Növbəti N sətirdə şəhərin xəritəsi olan M ədəd verilir.
Birinci sətirdə mutantın ödəməli olduğu minimal cərimənin ölçüsünü göstərən bir tam ədəd çıxarın.
İkinci sətirdə yolda olan kəsişmələrin sayını çıxarın.
Növbəti sətirlərdə heyvanın keçəcəyi kəsişmələrin koordinatlarını çıxarın. Cərimənin 10^9-u keçməyəcəyi təmin edilir.
Nümunə 1