#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)
using namespace std;
void allocate_tickets(vector< vector<int> > s);
long long find_maximum(int k, vector< vector<int> > x) {
int n = x.size();
int m = x[0].size();
//long long ans = 0;
//vector< vector<bool> > minval(n, vector<bool>(k, true));
//vector< vector<bool> > plusval(n, vector<bool>(k, false));
vector< pair<int, int> > last_coor(n, make_pair(m - 1, k - 1));
priority_queue< pair<int, int> > q;
forint(i, n) {
q.push(make_pair(x[i][k - 1] + x[i][m - 1], i));
}
forint(i, k * n / 2) {
auto pos = q.top();
q.pop();
//minval[pos.second][last_coor[pos.second].first] = false;
last_coor[pos.second].first--;
last_coor[pos.second].second--;
if (last_coor[pos.second].second >= 0) {
q.push({x[pos.second][last_coor[pos.second].first] + x[pos.second][last_coor[pos.second].second], pos.second});
}
}
/*
for (auto& i : minval) {
for (auto& j : i) {
cerr << minval << endl;
}
}
for (auto a : last_coor) {
cerr << a.first << "---" << a.second << endl;
}
*/
vector< vector<int> > round(n, vector<int> (m, -1));
long long val = 0;
forint(i, k) {
vector< pair<int, int> > v(n);
forint(j, n) {
v[j].first = last_coor[j].first;
v[j].second = j;
}
sort(v.begin(), v.end());
for(int j = 0; j < n/2; j++) {
val += x[v[j].second][last_coor[v[j].second].first + 1];
round[v[j].second][last_coor[v[j].second].first + 1] = i;
last_coor[v[j].second].first++;
}
for(int j = n/2; j < n; j++) {
val -= x[v[j].second][last_coor[v[j].second].second];
round[v[j].second][last_coor[v[j].second].second] = i;
last_coor[v[j].second].second--;
}
}
allocate_tickets(round);
return val;
}
