#include"tickets.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
struct data{
int first,second,val,col;
};
data mk(int a,int b,int c,int d){
data res;
res.first=a;
res.second=b;
res.val=c;
res.col=d;
return res;
}
bool cmp(data l,data r){
return l.val<r.val;
}
int game[1505],cnt[1505];
long long find_maximum(int k,vector<vector<int>>x){
int n=x.size();
int m=x[0].size();
vector<vector<int>>answer(n,vector<int>(m,-1));
vector<data>v;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
for(int l=j+1;l<m;l++)v.push_back(mk(j,l,x[i][j]+x[i][l],i));
long long res=0;
sort(v.begin(),v.end(),cmp);
for(auto cur:v){
if(game[cur.first]==(n>>1))continue;
if(answer[cur.col][cur.first]!=-1)continue;
res-=x[cur.col][cur.first];
game[cur.first]++;
answer[cur.col][cur.first]=(cnt[cur.col]++);
}
reverse(v.begin(),v.end());
for(int i=0;i<1505;i++)cnt[i]=game[i]=0;
for(auto cur:v){
if(game[cur.second]==(n>>1))continue;
if(answer[cur.col][cur.second]!=-1)continue;
res+=x[cur.col][cur.second];
game[cur.second]++;
answer[cur.col][cur.second]=(cnt[cur.col]++);
}
allocate_tickets(answer);
return res;
}
