#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1501
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int a[MAXN];
int cnt[MAXN][2];
bool vis[MAXN][MAXN];
ll find_maximum(int k, vector<vector<int>> x){
int n, m, mx, o, t;
n = x.size();
m = x[0].size();
mx = n * k / 2;
vector<pii> v;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
v.append({x[i][j], i});
sort(all(v));
reverse(all(v));
t = 0;
ll answer = 0;
for(auto & [i, j] : v){
if(cnt[j][1] == n / 2)
continue;
a[j]++;
t++;
if(t == mx) break;
}
for(int i = 0; i < n; i++)
cnt[i][1] = 0;
vector<vector<int>> ans = x;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
ans[i][j] = -1;
vector<int> w[2];
vector<pair<int, pii>> u;
vector<int> z;
for(int i = 0; i < n; i++)
z.append(i);
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(all(z), g);
for(auto & i : z){
for(int r = 0; r < k; r++){
u.append({cnt[r][0], {r, 0}});
u.append({cnt[r][1], {r, 1}});
}
for(int s = 0; s < k - a[i]; s++){
w[0].append(s);
answer -= x[i][s];
}
for(int s = m - a[i]; s < m; s++){
w[1].append(s);
answer += x[i][s];
}
sort(all(u));
for(auto & r : u){
if(w[r.ss.ss].empty() || vis[r.ss.ff][i] == 1 || r.ff == n / 2 || ans[i][w[r.ss.ss].back()] >= 0)
continue;
ans[i][w[r.ss.ss].back()] = r.ss.ff;
cnt[r.ss.ff][r.ss.ss]++;
vis[r.ss.ff][i] = 1;
w[r.ss.ss].pop_back();
}
w[0].clear();
w[1].clear();
u.clear();
}
allocate_tickets(ans);
return answer;
}
