#include<tickets.h>
#include<bits/stdc++.h>
#define xx second.first
#define yy second.second
#define fi first
#define se second
#define pii pair<int, pair<int, int>>
#define pi pair<int, int>
#define ll long long
using namespace std;
const int N = 1505;
vector<int> add[N], minu[N];
long long find_maximum(int k, vector<vector<int>> x)
{
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans;
ans.resize(n);
for(int i = 0; i < n; i++)
{
ans[i].resize(m);
for(int j = 0; j < m; j++)
ans[i][j] = -1;
}
priority_queue<pii, vector<pii>> q;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
q.push({x[i][j] + x[i][m - k + j], {i, j}});
ll kq = 0;
for(int i = 0; i < n * k / 2; i++)
{
pii tmp = q.top();
q.pop();
kq += x[tmp.xx][m - k + tmp.yy];
add[tmp.xx].push_back(m - k + tmp.yy);
// cout << tmp.xx << '\n';
}
for(int i = 0; i < n * k / 2; i++)
{
pii tmp = q.top();
q.pop();
kq -= x[tmp.xx][tmp.yy];
minu[tmp.xx].push_back(tmp.yy);
// cout << tmp.xx << '\n';
}
for(int i = 0; i < k; i++)
{
priority_queue<pi, vector<pi>> tmp;
for(int j = 0; j < n; j++)
tmp.push({add[j].size(), j});
for(int j = 0; j < n / 2; j++)
{
pi haha = tmp.top();
ans[haha.se][add[haha.se].back()] = i;
tmp.pop();
add[haha.se].pop_back();
}
while(!tmp.empty())
{
pi haha = tmp.top();
ans[haha.se][minu[haha.se].back()] = i;
tmp.pop();
minu[haha.se].pop_back();
}
}
// cout << kq << '\n';
// for(int i = 0; i < n; i++)
// {
// for(int j = 0; j < m; j++)
// cout << ans[i][j] << " ";
// cout << '\n';
// }
allocate_tickets(ans);
return kq;
}
//int main ()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// int k = 2;
// vector<vector<int>> huhu;
// huhu.resize(2);
// huhu[0] = {0, 2, 5};
// huhu[1] = {1, 1, 3};
//// huhu[2] = {3, 6};
//// huhu[3] = {2, 7};
// find_maximum(k, huhu);
// return 0;
//}
