Nə üçün inək yolu keçdi (Qızıl)#10538
Fermer Conun fermasi n \times n ölçülü kvadrat şəklində sahə şəbəkəsidir. Fermanın daxilində qonşu sahələri bir-birindən ayıran şimaldan-cənuba n - 1 yol və şərqdən-qərbə n - 1 yol keçir. Fermanın perimetri boyunca inəklərin fermanı tərk etməsinə imkan verməyən hündür hasar qurulub. İnək Bessi istənilən sahədən ona qonşu olan istənilən sahəyə (şimala, şərqə, cənuba və ya qərbə) sərbəst şəkildə keçə bilər, ancaq iki sahəni ayıran yoldan keçməzdən əvvəl hər iki tərəfə diqqətlə baxmalıdır. Bir yoldan keçmək onun vahid vaxtını alır.
Bir gün Fermer Con dostluq şahmat partiyası oynamaq üçün Bessini öz evinə dəvət edir. Bessi öz yolunu şimal-qərb küncündə yerləşən sahədən başlayır, Fermer Conun evi isə cənub-şərq küncündəki sahədə yerləşir, buna görə də Bessini kifayət qədər uzun yol gözləyir. Yol boyunca o acır və ziyarət etdiyi hər üçüncü sahədə (başlanğıc sahə hesaba alınmır, lakin dayanacağı son sahə Fermer Conun evi olan sahə ola bilər) dayanıb ot yeyir. Bəzi sahələr digərlərinə nisbətən daha yaxşı otla örtülüdür, buna görə də Bessinin dayanıb ot yeməsi üçün lazım olan vaxt onun dayandığı sahədən asılıdır.
Bessiyə Fermer Conun evinə çata biləcəyi minimum vaxtı müəyyən etməkdə kömək edin.
Birinci sətirdə n~(3 \le n \le 100) və t~(0 \le t \le 10^6) verilir. Növbəti sətirdə hər birində müsbət tam ədəd (hər biri 10^5-dən çox olmayaraq) verilir, bunlar hər bir sahədə ot yemək üçün lazım olan vaxtı təsvir edir. Birinci sətirin birinci ədədi şimal-qərb küncündəki sahəyə uyğundur.
Bessinin Fermer Conun evinə çatması üçün lazım olan minimum vaxtı çap edin.
Bu nümunədə optimal marşrut şərqə sahə getmək və ot yeməkdən ibarətdir ki, bu da vahid vaxt aparır, sonra cənuba iki sahə və şərqə bir sahə getmək və ot yemək vahid vaxt aparır, və nəhayət, cənuba bir sahə və şərqə bir sahə getməklə məqsədə çatmaqdan ibarətdir.
Nümunə 1