#include <bits/stdc++.h>
using namespace std;
//#define int int64_t
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define mp make_pair
#define vii vector<vector<int>>
#define ll long long
const int N = 2e5 + 5;
void allocate_tickets(vii a);
struct ticket{
int color, order, value;
};
bool operator < (const ticket &x, const ticket &y) {
return x.value < y.value;
}
int64_t find_maximum(int k, vii a) {
function<int64_t()> sub1 = [&]() {
int n = a.size();
vector<int> v(n);
rep(i, 0, n - 1) v[i] = a[i][0];
sort(all(v));
int bound = v[n / 2];
int64_t prize = 0;
rep(i, 0, n - 1) prize += abs(v[i] - bound);
rep(i, 0, n - 1) a[i][0] = 0;
allocate_tickets(a);
return prize;
};
function<int64_t()> sub2 = [&]() {
int n = a.size(), m = a[0].size();
vector<bool> vst(n);
vector<ticket> v;
rep(i, 0, n - 1) rep(j, 0, m - 1) {
v.push_back({i, j, a[i][j]});
}
sort(all(v));
int64_t prize = 0;
int minus = 0, add = 0, bound;
rep(i, 0, v.size() - 1) {
if (vst[v[i].color]) continue;
prize -= v[i].value;
a[v[i].color][v[i].order] = 0;
++add;
vst[v[i].color] = 1;
if (add == n / 2) {
bound = add;
break;
}
}
rep(i, 0, v.size() - 1) {
if (vst[v[i].color]) continue;
prize += v[i].value;
a[v[i].color][v[i].order] = 1;
++minus;
vst[v[i].color] = 1;
if (minus == n / 2) {
break;
}
}
rep(i, 0, n - 1) rep(j, 0, m - 1) --a[i][j];
allocate_tickets(a);
prize += 1ll * bound * n;
return prize;
};
return sub2();
}
// int main() {
// int n, m, k; cin >> n >> m >> k;
// vii a(n, vector<int> (m));
// rep(i, 0, n - 1) rep(j, 0, m - 1) cin >> a[i][j];
// cout << find_maximum(k, a);
// }
