Məktəb
Petryk Pyatoçkin məktəbdə oxuyur. Keçən il o, məktəbə trolleybusla gedirdi, lakin biletlərin qiymətinin artmasından sonra piyada getməyin daha sürətli və rahat olduğunu anladı. Petrykın yaşadığı İdeal şəhəri, m×n ölçüsündə kvadrat bloklardan ibarət məhəllələrdən təşkil olunmuş düzbucaqlı bir ərazidir. Şəhərin sərhədi məhəllələrin sərhədləri boyunca deyil, onları yarıya bölərək və ya künc məhəllələrdən dörddə birini "kəsərək" keçir — şəhərin sxeminə şəkil 1-də baxın.
Şəkil 1. İdeal şəhərin sxemi. Şəhərin sərhədləri qalın qara xəttlə göstərilib.
Petryk şəhərin ən cənub-şərq küncündən məktəbə gedir və məktəbin girişi olan ən şimal-qərb küncünə doğru irəliləyir. Başlanğıc və son nöqtələr şəkil 1-də qalın nöqtələrlə göstərilib. Oğlan yalnız məhəllələrin sərhədləri boyunca hərəkət edə bilər (məhəllələrin özləri tikilmişdir) və yalnız küçənin istiqamətinə perpendikulyar olaraq bir məhəllənin zirvəsindən qonşu məhəllənin zirvəsinə keçə bilər — şəhərin sərhədlərinə paralel. Hər bir kəsişmə üçün şərqdən qərbə və əksinə olan üfüqi və şimaldan cənuba və geri olan şaquli hərəkətin müddəti t ilə müəyyən edilir. Hər bir işıqfor belə işləyir: ilk t saniyə ərzində işıqfor üfüqi hərəkətə icazə verir və şaquli hərəkəti qadağan edir, növbəti t saniyə ərzində şaquli hərəkətə icazə verir (və üfüqi hərəkəti qadağan edir), (2t+1)-ci saniyədən 3t-ci saniyəyə qədər yenidən üfüqi hərəkətə icazə verir və s. Fərqli kəsişmələr üçün bu dəyər t fərqli ola bilər. Petryk bir məhəllənin bir tərəfini bir dəqiqəyə keçə bilər. Oğlan küçəni bir saniyəyə keçir — işıqforlar buna icazə verdikdə. Petryk qırmızı işıqda keçmək və şəhərin sərhədlərini aşmaq istəmir — bu çox təhlükəlidir.
Petrykə məktəbə çatmaq üçün ən qısa müddəti müəyyən etməyə kömək edin. Məlumdur ki, Petryk evdən çıxanda bütün işıqforlar üfüqi hərəkətə icazə verir.
Giriş verilənləri
Birinci sətirdə şəhərin eni və hündürlüyü olan m və n natural ədədləri göstərilib. Bu ədədlər 250-dən çox deyil.
Sonra n sətir gəlir. i və j üçün, 1 ≤ i ≤ n, 1 ≤ j ≤ m, j-ci ədəd (i+1)-ci sətirdə müvafiq kəsişmədə hərəkətin müddətidir. Bu ədəd naturaldır və 500-dən çox deyil. Hər sətirdə kəsişmələr ən qərbdən ən şərqə qədər sadalanır, birinci sətirdə ən şimal kəsişmələr təsvir edilir, sonuncuda isə ən cənub kəsişmələr.
Çıxış verilənləri
Petrykə məktəbə çatmaq üçün kifayət edəcək ən qısa müddətin (saniyələrlə) müddətini çıxarın.
Nümunəyə izah
Petryk məktəbə 187 saniyəyə çata bilər: o, evdən çıxacaq və dərhal üfüqi istiqamətdə yolu keçəcək; işıqforun şaquli istiqamətdə hərəkətə icazə verməsini gözləyəcək 2 saniyə və şimal istiqamətində yolu keçəcək; məhəllənin əks küncünə 120 saniyəyə çatacaq və müvafiq işıqfor üfüqi hərəkətə icazə verəcəyi üçün dərhal yolu keçəcək və şərq istiqamətində hərəkət etməyə davam edəcək, növbəti kəsişməyə çatana qədər. O, şaquli istiqamətdə yolu keçməyə icazə verildiyi son saniyədə yolu keçməyə vaxt tapacaq və dərhal son dəfə yolu keçəcək və məktəbə çatacaq. Petrykın yolu sxemdə göstərilib. Sxemdəki məhəllənin küncündəki rəqəm, Petrykın bu küncə çatmaq üçün sərf etməli olduğu saniyələrin sayını göstərir.
Asanlıqla görmək olar ki, oğlan məktəbə 187 saniyədən daha sürətli çata bilməz. Həqiqətən, əgər Petryk ümumiyyətlə yaşıl işığı gözləməsəydi, məktəbə ən tez 185 saniyəyə çata bilərdi (o, üç dəfə məhəllələr boyunca keçməli və beş dəfə yolu keçməli idi). Digər tərəfdən, ilk dəfə şimal istiqamətində yolu keçməzdən əvvəl — şərq istiqamətində neçə məhəllə keçsə də — oğlan ən azı 2 saniyə gözləməlidir.
Şəkil 2. Verilən nümunə giriş məlumatları üçün Petrykın məktəbə optimal yollarından biri.