using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApp { class Solution { private int[,] map; private int n, m, k; private int[] dx = new int[] { 1, 0, -1, 0 }; private int[] dy = new int[] { 0, 1, 0, -1 }; public Solution(ref int[,] map, int n, int m, int k) { this.n = n; this.m = m; if (k % 2 == 0) { this.k = k - 1; } else { this.k = k; } this.map = (int[,])map.Clone(); } public int Solve() { int sum = 0, result = 0; solve(0, 0, 1, ref sum, ref result); return result; } private void solve(int x, int y, int p, ref int sum, ref int result) { sum += map[x, y]; if (p == k) { if (x == 0 && y == 0 && sum > result) { result = sum; return; } } else { for (int i = 0; i < 4; i++) { int xx = (x + dx[i]), yy = (y + dy[i]); if ((0 <= xx && xx < n) && (0 <= yy && yy < m)) { solve(xx, yy, p + 1, ref sum, ref result); sum -= map[xx, yy]; } } } } } class Program { static void Main(string[] args) { int n, m, k; string param = Console.ReadLine(); string[] splitParam = param.Split(new Char[] { ' ' }); n = int.Parse(splitParam[0]); m = int.Parse(splitParam[1]); k = int.Parse(splitParam[2]); int[,] map = new int[n, m]; for (int i = 0; i < n; i++) { string line = Console.ReadLine(); string[] splitEnter = line.Split(new Char[] { ' ' }); for (int j = 0; j < m; j++) map[i, j] = int.Parse(splitEnter[j]); } Solution solution = new Solution(ref map, n, m, k); Console.WriteLine(solution.Solve()); } } }