Niyə inək yolu keçdi (Qızıl)
Conun ferması n * n ölçüsündə kvadrat sahələrdən ibarət bir şəbəkədir və burada n − 1 şimal-cənub və n − 1 qərb-şərq istiqamətində yollar mövcuddur. Bu yollar sahələr arasında separator rolunu oynayır. Fermanın xarici perimetri boyunca hündür bir çəpər inşa edilib ki, bu da inəklərin fermadan çıxmasına mane olur. Bessi istənilən sahədən qonşu sahəyə (şimal, cənub, qərb, şərq) sərbəst hərəkət edə bilər və hər bir yoldan keçmək üçün t vaxt vahidi sərf edir.
Bir gün FD Bessini şahmat oynamaq üçün evinə dəvət edir. Bessi fermanın şimal-qərb künc sahəsindən başlayır, FD-nin evi isə cənub-şərq künc sahəsində yerləşir. Bessi yol boyu acdığından, hər üçüncü ziyarət etdiyi sahədə ot yemək üçün dayanır (başlanğıc sahə daxil deyil, amma FD-nin evi olan son sahə daxil ola bilər). Bəzi sahələr digərlərindən daha çox otla zəngindir, buna görə də o, ot yemək üçün sərf edəcəyi vaxt sahədən asılıdır.
Bessiyə FD-nin evinə çatmaq üçün lazım olan minimum vaxtı müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir n (3 ≤ n ≤ 100) və t (0 ≤ t ≤ 10^6) ədədlərini ehtiva edir. Növbəti n sətirin hər biri n müsbət tam ədəd ehtiva edir (hər biri 10^5-dən çox deyil), hər sahədə ot yemək üçün tələb olunan vaxtı təsvir edir. Birinci sətirdəki birinci ədəd şimal-qərb küncüdür.
Çıxış Məlumatları
Bessinin FD-nin evinə çatmaq üçün tələb olunan minimum vaxtı çıxış edin.
İzah
Bu nümunədə optimal həll 3 hüceyrə şərqə hərəkət etməyi (ot yemək üçün 10 sərf edirik), sonra iki dəfə cənuba və bir dəfə şərqə hərəkət etməyi (ot yemək üçün 5 sərf edirik) və nəhayət, cənuba və şərqə hədəfə doğru hərəkət etməyi əhatə edir.