#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<pll> 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));
ll answer = 0;
t = 0;
for(auto & i : v){
if(cnt[i.ss][1] == n / 2)
continue;
a[i.ss]++;
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;
for(int i = n - 1; i >= 0; i--){
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();
mx -= o;
}
allocate_tickets(ans);
return answer;
}
