// dinamit.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
int N, M, K;
cin >> N >> M >> K;
vector<vector<int>>sum(N, vector<int>(M, 0));
vector<vector<int>>faradtsag(N, vector<int>(M, 0));
//vector<vector<int>>paratlandb(N, vector<int>(M, 0));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> faradtsag[i][j];
}
}
sum[0][0] = faradtsag[0][0];
/*if (faradtsag[0][0] % 2 == 1)
{
paratlandb[0][0]++;
}*/
for (int i = 1; i < M; i++)
{
sum[0][i] = sum[0][i - 1] + faradtsag[0][i];
/*if (faradtsag[0][i] % 2 == 1)
{
paratlandb[0][i]++;
}*/
}
for (int i = 1; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (j == 0)
{
sum[i][j] = sum[i - 1][0] + faradtsag[i][j];
}
else
{
if (sum[i - 1][j]< sum[i][j - 1])
{
sum[i][j] = sum[i - 1][j] + faradtsag[i][j];
//paratlandb[i][j] += paratlandb[i - 1][j];
}
else //if (sum[i - 1][j] < sum[i][j - 1])
{
sum[i][j] = sum[i][j-1] + faradtsag[i][j];
//paratlandb[i][j] += paratlandb[i][j-1];
}
/*else
{
if (paratlandb[i][j - 1]< paratlandb[i-1][j])
{
sum[i][j] = sum[i][j-1] + faradtsag[i][j];
paratlandb[i][j] += paratlandb[i ][j- 1];
}
else
{
sum[i][j] = sum[i-1][j] + faradtsag[i][j];
paratlandb[i][j] += paratlandb[i-1][j];
}
}*/
}
/*if (faradtsag[i][j] % 2 == 1)
{
paratlandb[i][j]++;
}*/
}
}
//int ertek= sum[N-1][M-1];
priority_queue<int>robbantas;
pair<int, int>akt;
robbantas.push(faradtsag[N - 1][M - 1]);
akt.first = N - 1;
akt.second = M - 1;
while (akt.first > 0 && akt.second > 0)
{
if (sum[akt.first - 1][akt.second] < sum[akt.first][akt.second - 1])
{
akt.first--;
}
else if (sum[akt.first - 1][akt.second] > sum[akt.first][akt.second - 1])
{
akt.second--;
}
else
{
if (faradtsag[akt.first - 1][akt.second]%2==0&&faradtsag[akt.first][akt.second - 1]%2==1)
{
akt.first--;
}
else
{
akt.second--;
}
}
/*else {
if (paratlandb[akt.first][akt.second - 1] < paratlandb[akt.first - 1][akt.second])
{
akt.first--;
}
else
{
akt.second--;
}
}*/
robbantas.push(faradtsag[akt.first][akt.second]);
}
while (akt.first > 0)
{
akt.first--;
robbantas.push(faradtsag[akt.first][akt.second]);
}
while (akt.second > 0)
{
akt.second--;
robbantas.push(faradtsag[akt.first][akt.second]);
}
int x;
int y;
for (int i = 0; i < K; i++)
{
/*x=robbantas.top();
if (x%2==0)
{
x = x / 2;
y = x;
}
else
{
x = x / 2;
y=x+1;
}
ertek -= y;*/
robbantas.push(robbantas.top() / 2);
robbantas.pop();
}
int ertek = 0;
while (robbantas.size() > 0)
{
ertek += robbantas.top();
robbantas.pop();
}
cout << ertek << endl;
return 0;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file