Marşrut 2

Verilmiş matris $n\times n$ ölçüsündədir və təbii ədədlərlə doldurulub. Matris üzrə yol sol yuxarı küncdən başlayır. Bir gedişdə şaquli və ya üfüqi qonşu xanaya keçmək olar (əgər belə xana varsa). Diaqonal üzrə hərəkət etmək və yerində qalmaq qadağandır. Uzunluğu $k$ olan yol üzrə xanalardakı ədədlərin maksimum cəmini tapmaq tələb olunur (xananı bir neçə dəfə ziyarət etmək olar).

Giriş məlumatları

Birinci sətirdə boşluqla ayrılmış $n$ və $k$ ədədləri verilir $(2\le n\le 100,1\le k\le 2000)$. Sonra matris $n$ sətirdən ibarət olur, hər sətirdə $n$ ədəd var. Matrisin bütün elementləri tam ədədlərdir və $1$ ilə $9999$ arasında qiymət alır.

Çıxış məlumatları

Bir ədəd çıxarın - maksimum cəmi.

Nümunələr