YVQ LQŞ-də#4052
Kolya, doqquzuncu sinif şagirdi, yaxınlarda Yay Kinematoqrafiya Məktəbinə qoşulub və ilk olaraq kinostudiyanı ziyarət etmək qərarına gəlib. Məktəb "Orlyatko" uşaq düşərgəsində keçirilir və burada bir-birini kəsən çoxlu asfalt yollar mövcuddur. Bu düşərgənin özəlliyi ondadır ki, bütün yollar və kəsişmələr işarələnib və burada hərəkət qaydaları tətbiq olunur – qayda pozuntusuna görə cərimə tətbiq edilir.
Kinostudiya Kolyanın yaşadığı evdən cənub-şərqdə yerləşir, ona görə də o, yalnız şərq və cənub istiqamətində hərəkət etməyi planlaşdırır. Kinostudiyaya tez çatmaq istədiyi üçün Kolya qaydalara məhəl qoymadan kəsişmələrdən sərbəst keçmək fikrindədir. Lakin o, SCS-də məsuliyyətli şagird kimi qayda pozuntularından doğan cərimələrin cəmini minimuma endirmək istəyir. Sənin vəzifən ona bu işdə kömək etməkdir.
Düşərgənin xəritəsi N \times M ölçülü bir tor kimi verilir. -ci sətirdə və -ci sütunda yerləşən hər bir kəsişmədə həmin kəsişmədən keçmək üçün tələb olunan cərimə göstərilib. Bütün indekslər 1-dən başlayır (1 \leq i \leq N, 1 \leq j \leq M).
Kolyaların evi düşərgənin şimal-qərb küncündə, kinostudiya isə cənub-şərq küncündə yerləşir. Məqsədin, Kolyanın minimum cərimə ödəməklə kinostudiyaya çata biləcəyi marşrutu tapmaqdır.
Girişin birinci sətrində torun ölçülərini göstərən iki natural ədəd və (1 \leq N, M \leq 1000) verilir.
Sonra gələn sətrin hər birində "Orlyatko" düşərgəsindəki uyğun sətrin kəsişmələrinə aid cərimələr verilmişdir.
Birinci sətrdə Kolyanın ödəməli olduğu minimum cəriməni bir tam ədəd kimi yazın. İkinci sətrdə marşrutdakı kəsişmələrin sayını göstərin. Sonrakı sətirlərdə isə Kolyanın start nöqtəsindən son nöqtəyə (N, M) kimi hərəkəti zamanı keçəcəyi kəsişmələrin koordinatlarını ardıcıllıqla göstərin. Hər sətrdə iki tam ədəd: və (1 \leq i \leq N, 1 \leq j \leq M) olmalıdır.
Zəmanət verilir ki, cəmi cərimə 10^9-u keçməyəcək.
Nümunə 1