#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define pb push_back
#define eb emplace_back
#define SZ(a) ((int)a.size())
#define REP(i,n) for(int i=0;i<(n);i++)
const int maxn = 1505;
int n,m,k;
std::vector<std::vector<int>> ans;
vector<int> idx[maxn]; //pos
vector<int> idx2[maxn]; //neg
set<pii> st;
void distribute(){//distrubute all tickets in idx[] to k rounds, each round with n/2 distinct color
REP(i,n){
st.insert(MP(SZ(idx[i]),i));
}
REP(i,k){
auto it = prev(st.end());
vector<int> clr={};
bool vis[maxn]={0};
REP(j,n/2){
clr.pb(it->S);
--it;
}
for(int j:clr){
vis[j] = 1;
ans[j][idx[j].back()] = i;
st.erase(MP(SZ(idx[j]),j));
idx[j].pop_back();
st.insert(MP(SZ(idx[j]),j));
}
REP(j,n) if(!vis[j]){
ans[j][idx2[j].back()] = i;
idx2[j].pop_back();
}
}
}
// bool check(vector<int> v){
// assert(SZ(v)==n);
// sort(ALL(v));
// reverse(ALL(v));
// int sum = 0;
// REP(i,SZ(v)){
// sum+=v[i];
// if(sum>(i+1) * k) return 0;
// }
// return 1;
// }
ll val[maxn][maxn];
priority_queue<pll> pq;
int iter[maxn];
long long find_maximum(int _k, std::vector<std::vector<int>> a) {
n = a.size();
m = a[0].size();
k=_k;
ans.resize(n);
REP(i,n) ans[i].resize(m);
REP(i,n) REP(j,m) ans[i][j]=-1;
ll ret = 0;
REP(i,n){
REP(j,k) ret -= a[i][j];
REP(j,k){
val[i][j] = a[i][m-1-j] + a[i][k-1-j];
}
}
REP(i,n) iter[i] = 0;
REP(i,n) pq.push(MP(val[i][0],i));
REP(T,n*k/2){
auto cur = pq.top();
pq.pop();
int idx = cur.S;
ret += cur.F;
iter[idx]++;
if(iter[idx]==k) continue;
pq.push(MP(val[idx][iter[idx]],idx));
}
// REP(i,n) cout<<iter[i]<<" \n"[i==n-1];
{
REP(i,n){
REP(j,k-iter[i])
idx2[i].pb(j);
REP(j,iter[i])
idx[i].pb(m-1-j);
}
// REP(i,n) {
// for(int j:idx[i]) cout<<j<<' ';
// cout<<'\n';
// }
distribute();
}
allocate_tickets(ans);
return ret;
}
