// :)^2
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
const int maxn5 = 2e3 + 10;
pair <int, int> per[maxn5];
int cnt[maxn5];
vector <int> req[maxn5][2];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> ret;
for (int i = 0; i < n; i++) {
for(int j = 0; j < m; j++)
cnt[i] += x[i][j];
vector <int> row(m);
fill(all(row), -1);
ret.push_back(row);
}
ll ans = 0;
int rem = m, num = 0;
while(k--){
ans += n / 2;
for(int i = 0; i < n; i++)
per[i] = {cnt[i], i};
sort(per, per + n);
for(int i = 0; i < n / 2; i++){
if(rem - per[i].fi > 0)
req[per[i].se][0].pb(num);
else{
ans--;
cnt[per[i].se]--;
req[per[i].se][1].pb(num);
}
}
for(int i = n / 2; i < n; i++){
if(per[i].fi > 0){
req[per[i].se][1].pb(num);
cnt[per[i].se]--;
}
else{
ans--;
req[per[i].se][0].pb(num);
}
}
rem--;
num++;
}
for(int i = 0; i < n; i++){
int pt = 0;
for(auto id : req[i][0])
ret[i][pt++] = id;
pt = m - 1;
for(auto id : req[i][1])
ret[i][pt--] = id;
}
allocate_tickets(ret);
return ans;
}
