Xanlar#8557
Elli bu yaxınlarda Bolqar xanları haqqında öyrəndi - qitə boyunca yüzillərlə səyahət edən köçəri xalqların hökmdarları, nəhayət, Bolqarıstanın indiki ərazilərində məskunlaşana qədər.
Onların dolaşdığı qitə n * m bölgələrə bölünmüşdür, n sətir və m sütunlu düzbucaqlı formada yerləşmişdir. Xanlar müəyyən bir bölgədə dəqiq bir il qalırdılar və orada yaşadıqları müddətdə klanları həmin bölgədəki bütün yeməyi yeyirdi. İlin sonunda onlar yan tərəfdəki dörd qonşu bölgədən birinə köçürdülər, orada növbəti ili keçirirdilər, oradakı bütün yeməyi yeyirdilər və s. Qonşu bölgəyə köçmənin dərhal baş verdiyini düşünəcəyik (axı, bir neçə günlük səyahət bir il ilə müqayisədə nədir). Xanlar heç vaxt ardıcıl iki il eyni bölgədə qalmırdılar, bu halda klanları aclıqdan ölə bilərdi.
Hər bir bölgə üçün orada ola biləcək maksimum yemək miqdarı məlumdur. Bu dəyəri tam ədəd A[ij] ilə ifadə edək. Xanlar bölgədəki bütün yeməyi yeyib klanları ilə qonşu bölgəyə köçdükdən sonra, oradakı yemək bərpa olunmağa başlayırdı. Xanların bölgədən ayrılmasından bir il sonra bölgədə 1 yemək vahidi yaranırdı. Bundan sonra hər il bölgədəki yemək miqdarı ikiqat artırdı, ta ki, həmin bölgə üçün maksimum dəyər A[ij]-ə çatana qədər. Qeyd edək ki, yemək miqdarı heç vaxt bölgədə ola biləcək maksimum miqdarı keçmirdi. Məsələn, əgər A[ij] = 55 olarsa, xanların bu bölgədən ayrılmasından sonrakı ilk on ilin hər birinin əvvəlində bu bölgədəki yemək miqdarı müvafiq olaraq 0, 1, 2, 4, 8, 16, 32, 55, 55, 55 idi.
Xanlar heç vaxt bölgəyə geri qayıtmırdılar, ta ki, oradakı yemək tam bərpa olunub maksimuma çatana qədər. Bu səbəbdən, məsələn, xanlar daha az yemək olan bir bölgəyə (məsələn, 42 vahid, amma bu maksimum miqdardır) köçə bilərdilər, daha çox yemək olan bir bölgəyə (məsələn, 64, amma maksimum 71) deyil. Əvvəlki paraqrafdakı nümunədə xanlar bölgəyə ayrılmalarından 8 il sonra geri qayıda bilərdilər, bu, həmin bölgədəki yemək miqdarının maksimum olduğu ilk ildir.
Elli qitənin hər bir bölgəsindəki maksimum yemək miqdarı haqqında məlumatı bilir, bu məlumat n sətir və m sütunlu A matrisi kimi verilir. Xanların ilk ili sol üst bölgədə keçirəcəklərini və başlanğıcda hər bir bölgənin həmin bölgə üçün mümkün olan maksimum yemək miqdarını ehtiva etdiyini bilə-bilə, xanların k il ərzində cəmi nə qədər maksimum yemək yeyə biləcəklərini müəyyənləşdirin.
Birinci sətir n, m (1 ≤ n, m ≤ 10) və k (1 ≤ k ≤ 100) tam ədədlərini ehtiva edir, bunlar müvafiq olaraq matrisin sətir və sütun sayını və illərin sayını göstərir. Növbəti n sətirdə hər biri m tam ədəd A[ij] (10 ≤ A[ij] ≤ 100) var, müvafiq bölgədəki maksimum yemək miqdarını göstərir. Həmişə bir yolun olacağı təmin edilir ki, bölgə tam bərpa olunana qədər təkrar ziyarət edilmə qaydasını pozmasın.
Bir tam ədəd çıxarın - xanların optimal səyahət edəcəkləri təqdirdə yeyə biləcəkləri maksimum cəmi yemək miqdarı.
Birinci nümunədə xanların maksimum yemək miqdarı (254 vahid) yemək üçün ziyarət edə biləcəkləri bölgələr - maksimum yemək miqdarı 11, 17, 13, 96, 15, 17, 22, 14, 16, 18, 15 olan bölgələrdir. Bu köçlərdə onlar yalnız bir bölgəni iki dəfə ziyarət edəcəklər - maksimum yemək miqdarı 15 olan bölgəni. Qeyd edək ki, xanların ziyarət etdiyi son bölgə ilə qonşu olan bütün bölgələr son ilin sonunda mümkün olan maksimum yemək miqdarını ehtiva etmir. Verilən test üçün bu problem deyil, çünki bu son ildir. Amma xanların köçlərini davam etdirmələri lazım olsaydı (məsələn, k 12 olsaydı, 11 deyil), başqa bir yol seçməli olardılar. Birinci nümunə üçün k = 12 üçün qitədə optimal yol variantı: 11, 17, 13, 96, 15, 18, 16, 17, 22, 14, 10, 24, cəmi 273.
Nümunə 1
Nümunə 2