#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
int a[n], b[n];
for (int i = 0; i < n; i++)
{
a[i] = 0;
b[i] = m - 1;
}
long long ret = 0;
for (int g = 0; g < k; g++)
{
vector<int>vals;
for (int i = 0; i < n; i++)
vals.push_back(x[i][a[i]]);
sort(vals.begin(), vals.end());
multiset<int>A, B;
for (int i = 0; i < n / 2; i++)
A.insert(vals[i]);
for (int i = n / 2; i < n; i++)
B.insert(vals[i]);
bool koks[n];
for (int i = 0; i < n; i++)
koks[i] = false;
bool ok = true;
auto add = [&](long long v)
{
if (v < *B.begin())
{
A.insert(v);
return -v;
}
else
{
B.insert(v);
return v;
}
};
auto eras = [&](int v)
{
long long ret = 0;
if (A.find(v) != A.end())
{
A.erase(A.find(v));
ret += v;
}
else
{
B.erase(B.find(v));
ret -= v;
}
while (A.size() < B.size())
{
auto it = B.begin();
int x = *it;
B.erase(it);
A.insert(x);
ret -= x * 2;
}
while (A.size() > B.size())
{
auto it = --A.end();
int x = *it;
A.erase(it);
B.insert(x);
ret += x * 2;
}
return ret;
};
while (ok)
{
ok = false;
for (int i = 0; i < n; i++)
{
int v1 = x[i][a[i]];
int v2 = x[i][b[i]];
if (koks[i])
swap(v1, v2);
if (add(v2) + eras(v1) > 0)
{
koks[i] = !koks[i];
ok = true;
}
else
{
add(v1);
eras(v2);
}
}
for (int i = 0; i < n; i++)
{
int v1 = x[i][a[i]];
int v2 = x[i][b[i]];
if (koks[i])
swap(v1, v2);
for (int j = 0; j < i; j++)
{
int w1 = x[j][a[j]];
int w2 = x[j][b[j]];
if (koks[j])
swap(w1, w2);
if (add(v2) + eras(v1) + add(w2) + eras(w1) > 0)
{
koks[i] = !koks[i];
koks[j] = !koks[j];
ok = true;
break;
}
else
{
add(v1);
eras(v2);
add(w1);
eras(w2);
}
}
}
}
for (int i = 0; i < n; i++)
if (koks[i])
{
answer[i][b[i]] = g;
b[i]--;
}
else
{
answer[i][a[i]] = g;
a[i]++;
}
for (int i : A)
ret -= i;
for (int i : B)
ret += i;
}
allocate_tickets(answer);
return ret;
}
