Хани#8557

Хани

1 секунда

128 мегабайтів

Легка

Еллі нещодавно дізналася про болгарських ханів — правителів кочових народів, які подорожували континентом сотні років, перш ніж остаточно оселитися на території сучасної Болгарії.

Континент, яким вони мандрували, поділений на $n \times m$ n \times m регіонів, розташованих у формі прямокутника з $n$ рядками і $m$ стовпцями. Хани зупинялися на один рік у певному регіоні, і за цей час їхній клан з'їдав усю їжу в цьому регіоні. Наприкінці року вони переміщалися в один із (не більше ніж) чотирьох сусідніх по стороні регіонів, де проводили наступний рік, з'їдаючи всю їжу там, і так далі. Вважатимемо, що переміщення в сусідній регіон відбуваються миттєво (зрештою, що таке кілька днів подорожі в порівнянні з цілим роком). Хани ніколи не залишалися два роки поспіль в одному регіоні, оскільки їхній клан міг би загинути від голоду.

Для кожного регіону відома максимальна кількість їжі, яка може в ньому бути. Позначимо це значення цілим числом $A_{ij}$ A_{ij}. Після того, як хани з'їдали всю їжу в регіоні та від'їжджали зі своїм кланом у сусідній регіон, їжа в ньому починала відновлюватися. Через рік після від'їзду ханів у регіоні з'являлася $1$ одиниця їжі. Після цього кожного року кількість їжі в регіоні подвоювалася, поки вона не досягала максимального значення $A_{ij}$ A_{ij} для цього регіону. Зверніть увагу, що кількість їжі ніколи не перевищувала максимальну кількість, яка могла бути в регіоні. Наприклад, якщо $A_{ij} = 55$ A_{ij} = 55, то кількість їжі в цьому регіоні на початку кожного з перших десяти років після від'їзду ханів з цього регіону була, відповідно, $0$ , $1$ , $2$ , $4$ , $8$ , $16$ , $32$ , $55$ , $55$ , $55$ .

Хани ніколи не поверталися в регіон, поки він не відновлювався повністю і кількість їжі в ньому не досягала максимуму. Через це могла скластися ситуація, що хани перемістилися в регіон, де менше їжі (скажімо, $42$ одиниці, але це максимальна кількість), а не в регіон, де більше їжі (скажімо, $64$ , а максимум $71$ ). У прикладі в попередньому параграфі хани могли б повернутися в регіон на початку $8$ року після свого від'їзду, це перший рік, у який у цьому регіоні кількість їжі максимальна.

Еллі знає інформацію про максимальну кількість їжі в кожному регіоні континенту, задану як матриця $A$ з $n$ рядками і $m$ стовпцями. Знаючи, що хани проведуть перший рік у лівому верхньому регіоні, а початково кожен регіон містить максимально можливу для цього регіону кількість їжі, з'ясуйте, яку максимальну кількість їжі хани зможуть сумарно з'їсти за $k$ років.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $m$ ( $1 \leq n, m \leq 10$ 1 \le n, m \le 10) і $k$ ( $1 \leq k \leq 100$ 1 \le k \le 100), що задають, відповідно, кількість рядків, кількість стовпців у матриці і кількість років. На кожному з наступних $n$ рядків знаходяться по $m$ цілих чисел $A_{ij}$ A_{ij} ( $10 \leq A_{ij} \leq 100$ 10 \le A_{ij} \le 100), що задають максимальну кількість їжі у відповідному регіоні. Гарантується, що завжди буде шлях, який не порушує правила, що не можна повторно відвідувати регіон до моменту, коли в ньому повністю відновиться максимальна кількість їжі.

Вихідні дані

Виведіть одне ціле число - максимальну сумарну кількість їжі, яку хани зможуть з'їсти, якщо вони будуть подорожувати оптимально.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі регіони, які хани можуть відвідати, щоб з'їсти максимальну кількість їжі ( $254$ одиниці) – регіони з максимальною кількістю їжі $11$ , $17$ , $13$ , $96$ , $15$ , $17$ , $22$ , $14$ , $16$ , $18$ , $15$ , відповідно. При цих переміщеннях вони відвідають двічі лише один регіон – з максимальною кількістю їжі $15$ . Зверніть увагу, що після останнього року всі регіони, сусідні з останнім регіоном, відвіданим ханами, не містять максимально можливої кількості їжі. Для наведеного тесту це не проблема, оскільки це останній рік. Але якби ханам потрібно було продовжити переміщення (наприклад, $k$ було б рівне $12$ , а не $11$ ), то їм довелося б обрати інший шлях. Варіант оптимального шляху для $k = 12$ k = 12 по континенту з першого прикладу: $11$ , $17$ , $13$ , $96$ , $15$ , $18$ , $16$ , $17$ , $22$ , $14$ , $10$ , $24$ , з сумою $273$ .