#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 1515;//100100*5;
const ll MOD = 1e9+7;
const ll INF = 2e9;
void allocate_tickets( std::vector<std::vector<int>> _d);
std::vector<std::vector<int>> res;
priority_queue<ipi> pq;
vector<int> v[MAXN], w[MAXN];
bitset<MAXN> chk;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
res.resize(n); for(auto &x:res) x.resize(m, -1);
ll ans=0;
for(int i=0; i<n; i++) {
for(int j=0; j<k; j++) {
pq.push(ipi(x[i][j]+x[i][j+m-k], pi(i,j+m-k)));
ans -= x[i][j]; w[i].push_back(j);
}
}
for(int i=0; i<k*n/2; i++) {
auto x = pq.top(); pq.pop();
ans += x.ff;
v[x.ss.ff].push_back(x.ss.ss);
w[x.ss.ff].pop_back();
}
for(int t=k; t>0; t--) {
int cnt = n/2; chk.reset();
for(int i=0; i<n; i++) {
if(v[i].size()==t) {
cnt--;
res[i][v[i].back()] = t-1;
v[i].pop_back();
chk[i] = 1;
}
}
for(int i=0; i<n; i++) {
if(cnt==0) break;
if(v[i].size()) {
cnt--;
res[i][v[i].back()] = t-1;
v[i].pop_back();
chk[i] = 1;
}
}
for(int i=0; i<n; i++) {
if(!chk[i]) {
res[i][w[i].back()] = t-1;
w[i].pop_back();
}
}
}
allocate_tickets(res);
return ans;
}
