Khans
Есенен Турнир по Информатика 2017
Time Limit: 2s, Memory Limit: 64MiB
Ели наскоро изучаваше българските ханове – владетели на номадски племена, които стотици години обикаляли континента преди най-накрая да се установят перманентно на едно място, където в момента се намира България.

Континентът, който обитавали, бил разделен на N * M региона, удобно подредени в правоъгълник с N реда и M колони. Хановете прекарвали една година в определен регион, през която те и тяхното племе консумирали всичката храна там. В края на годината те се премествали в някой от (до) четирите съседни по страна региони, където прекарвали следващата година (отново консумирайки всичката храна там), и т.н. Считаме преместването в съседен регион като събитие, случващо се моментално точно в края на годината (какво са няколко дни в път, в сравнение с цяла година?). Хановете никога не оставали в даден регион две или повече години, тъй като племето им би умряло от глад.

Всеки регион имал определено максимално количество храна, която можел да поддържа. Ще означим това максимално количество във всеки регион с цяло число Aij. След като хановете изконсумирали всичката храна от даден регион и се преместели в друг, регионът лека полека започвал да се възстановява. В годината веднага след изнасянето на хановете в региона се "завъждала" една единица храна. Годината след това храната се удвоявала, след това на третата година се удвоявала отново и т.н., докато достигнела максимума за региона Aij. Забележете, че количеството храна никога не превишавала максимума, който регионът можел да поддържа. Например, ако максимумът за някой регион е Aij = 55, количеството храна в началото на всяка от десетте години, следващи изнасянето на хановете от региона, би било, съответно, 0, 1, 2, 4, 8, 16, 32, 55, 55, 55 единици.

Хановете знаели, че не бива да се връщат в регион, преди той напълно да се е възстановил до максималното си количество. В противен случай те можело трайно да го увредят, което не искали да се случва. Поради това, понякога те предпочитали по-беден хранително регион (например с 42 единици храна) пред по-богат такъв (например, с 64 единици, но с максимум 71). В примера от предния параграф, те биха могли да се завърнат в региона в началото на осмата година след като са го напуснали, понеже тя е първата, в която регионът е отново на своя максимум.

Ели разполага с информация за континента под формата на матрица A с N реда и M колони, даваща максималната храна за всеки от регионите. Знаейки, че хановете прекарали първата си година в горния ляв ъгъл на матрицата, сега момичето се чуди какво е максималното количество храна, което са можели да изконсумират в период от K години?
Вход
На първия ред на стандартния вход ще бъдат зададени три цели числа N, M, и K, указвайки, съответно, броя редове, броя колони, и броя години. На следващите N реда ще бъдат зададени по M цели числа Aij, указващи максималното количество храна във всеки от регионите. Гарантирано е, че ще има валиден път с дължина K, който не нарушава изискването за връщане в регион само когато той се е възстановил напълно.
Изход
На единствен ред на стандартния изход изведете едно цяло число – максималното количество храна, което хановете можели да изконсумират ако пътуват оптимално.
Ограничения
  • 1 ≤ N, M ≤ 10
  • 1 ≤ K ≤ 100
  • 10 ≤ Ai ≤ 100
Примерен Вход Примерен Изход
4 4 11 11 17 13 96 10 12 18 15 13 12 16 17 24 10 14 22 254
7 10 27 92 33 98 66 51 65 50 28 17 65 81 26 35 90 51 79 16 49 26 68 94 16 61 45 20 31 99 75 51 73 17 83 11 75 59 56 15 24 63 44 83 32 80 49 60 83 85 98 17 76 16 75 81 97 89 50 80 34 79 64 26 64 59 37 14 30 20 58 46 66 2017
В първия пример регионите, които хановете могат да посетят за да изконсумират максимално количество храна (254 единици) могат да са тези със стойности, съответно, 11, 17, 13, 96, 15, 17, 22, 14, 16, 18, 15. С тази последователност те посещават само един регион повторно – последния (със стойност 15). Забележете, че след последната година всички съседни региони не са се възстановили до респективните им максимуми, тоест хановете не могат да се преселят никъде. Тъй като това е последната година, това не е проблем; ако, обаче, трябваше да пътуват още една година (тоест K беше 12 вместо 11), те трябваше да изберат друг път, тъй като оставайки в клетка не е възможно. Възможен път с K = 12 би бил 11, 17, 13, 96, 15, 18, 16, 17, 22, 14, 10, 24 за сума 273.
Мрън!