#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#include <set>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<ll, int>
const int N = 1502;
int n, m, k;
vector<vector<int>> x;
vector<vector<int>> answer;
ll ans;
set<pii> fid; // .first = sum, .second = index
pii cnt[N]; //.first = cnt, .second = index
int sig[N][N]; // +, =, -
int topj[N], botj[N];
void srt() {
auto it = fid.end();
it--;
int i = (*it).second;
fid.erase(*it);
sig[i][botj[i]] = 0;
botj[i]--;
topj[i]--;
sig[i][topj[i]] = 1;
cnt[i].first++;
if (botj[i] >= 0) {
fid.insert(pii(x[i][topj[i] - 1] + x[i][botj[i]], i));
}
}
void play(int j) {
sort(cnt, cnt + n);
for (int i = 0; i < n / 2; i++) {
int ii = cnt[i].second, jj = botj[ii];
answer[ii][jj] = j;
botj[ii]++;
}
for (int i = n / 2; i < n; i++) {
int ii = cnt[i].second, jj = topj[ii];
answer[ii][jj] = j;
topj[ii]--;
cnt[i].first--;
}
}
long long find_maximum(int klir, vector<vector<int>> xuy) {
k = klir;
x = xuy;
n = x.size();
m = x[0].size();
answer.resize(n);
for (int i = 0; i < n; i++) {
answer[i].resize(m, -1);
}
fill(topj, topj + n, m);
fill(botj, botj + n, k - 1);
for (int i = 0; i < n; i++) {
cnt[i] = pii(0, i);
for (int j = 0; j < k; j++) {
sig[i][j] = -1;
}
fid.insert(pii(x[i][topj[i] - 1] + x[i][botj[i]], i));
}
for (int i = 0; i < n * k / 2; i++) {
srt();
}
fill(topj, topj + n, m - 1);
fill(botj, botj + n, 0);
for (int j = 0; j < k; j++) {
play(j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += x[i][j] * sig[i][j];
}
}
allocate_tickets(answer);
return ans;
}
/*
2 3 2
0 2 5
1 1 3
4 2 1
5 9
1 4
3 6
2 7
2 2 2
1 1
1 1
*/
