Ханы
Элли недавно узнала про Булгарских ханов - правителей кочевых народов, которые путешествовали по континенту сотни лет, прежде чем они наконец поселились навсегда в местах, где сейчас находится Болгария.
Континент, по которому они скитались, разделен на n * m регионов, расположенных в форме прямоугольника с n строками и m столбцами. Ханы останавливались ровно на один год в определенном регионе, и пока они жили там, их клан съедал всю еду в этом регионе. В конце года они перемещались в один из (не более чем) четырех соседних по стороне регионов, там они проводили следующий год, съедая всю еду в нем, и так далее. Будем считать, что перемещения в соседний регион происходят мгновенно (в конце концов, что такое несколько дней путешествия по сравнению с целым годом). Ханы никогда не проводили два года подряд в одном регионе, в этом случае их клан мог бы погибнуть от голода.
Для каждого региона известно максимальное количество еды, которое может в нем находиться. Обозначим это значение целым числом A[ij].После того, как ханы съедали всю еду в регионе и уезжали со своим кланом в соседний регион, еда в нем начинала восстанавливаться. Через год после отъезда ханов в регионе появлялась 1 единица еды. После этого каждый год количество еды в регионе удваивалось, пока оно не достигало максимального значения A[ij] для этого региона. Обратите внимание, что количество еды никогда не превышало максимального количества, которое могло находиться в регионе. Например, если A[ij] = 55, то количество еды в этом регионе в начале каждого из первых десяти лет после отъезда ханов из этого региона, было, соответственно, 0, 1, 2, 4, 8, 16, 32, 55, 55, 55.
Ханы никогда не возвращались в регион, пока он не восстанавливался полностью и количество еды в нем не достигало максимума. Из-за этого могла, например, сложиться ситуация, что ханы переместились в регион, где меньше еды (скажем, 42 единицы, но это максимальное количество), а не в регион, где больше еды (скажем, 64, а максимум 71). В примере в предыдущем параграфе ханы могли бы вернуться в регион в начале 8 года после своего отъезда, это первый год, в который в этом регионе количество еды максимально.
Элли знает информацию о максимальном количестве еды в каждом регионе континента, заданную как матрицу A с n строками и m столбцами. Зная, что ханы проведут первый год в левом верхнем регионе, а исходно каждый регион содержит максимальное возможное для этого региона количество еды, выясните, какое максимальное количество еды ханы смогут суммарно съесть за k лет.
Входные данные
Первая строка содержит три целых числа n, m (1 ≤ n, m ≤ 10) и k (1 ≤ k ≤ 100), задающих, соответственно, количество строк, количество столбцов в матрице и количество лет. На каждой из следующих n строк находятся по m целых чисел A[ij] (10 ≤ A[ij] ≤ 100), задающих максимальное количество еды в соответствующем регионе. Гарантируется, что всегда будет путь, который не нарушает правила, что нельзя повторно посещать регион до момента, когда в нем полностью восстановится максимальное количество еды.
Выходные данные
Выведите одно целое число - максимальное суммарное количество еды, которое ханы смогут съесть, если они будут путешествовать оптимально.
Объяснение
В первом примере регионы, которые ханы могут посетить, чтобы съесть максимальное количество еды (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.