#include <bits/stdc++.h>
#ifndef LOCAL
#include "tickets.h"
#endif
using namespace std;
#ifdef LOCAL
void allocate_tickets(vector<vector<int>> ans){
int n = ans.size(), m = ans[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
cout << ans[i][j] << ' ';
cout << '\n';
}
}
#endif
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
int64_t a = 0;
priority_queue<array<int64_t, 4>> pq;
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<priority_queue<int>> maximum_in_row(n);
vector< priority_queue<int, vector<int>, greater<int>> > minimum_in_row(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
a -= int64_t(x[i][j]);
ans[i][j] = j;
minimum_in_row[i].push(j);
}
for(int j = m-1; j >= k; --j)
maximum_in_row[i].push(j);
pq.push({int64_t(x[i][k-1] + x[i][m-1]), i, k-1, m-1});
}
for(int i = 0; i < n*k / 2; i++){
auto [delta, row, remove, add] = pq.top();
pq.pop();
maximum_in_row[i].pop();
minimum_in_row[i].pop();
maximum_in_row[i].push(remove);
minimum_in_row[i].push(add);
ans[row][add] = ans[row][remove];
ans[row][remove] = -1;
a += int64_t(delta);
int nxtmin = minimum_in_row[row].top(), nxtmax = maximum_in_row[row].top();
pq.push({x[row][nxtmin] + x[row][nxtmax], row, nxtmin, nxtmax});
}
allocate_tickets(ans);
return a;
}
#ifdef LOCAL
int main(){
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> x(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> x[i][j];
cout << find_maximum(k, x) << '\n';
}
#endif
