#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=1505;
vll v[mxN][2];
ll ans[mxN][mxN];
}
long long find_maximum(int k, vector<vector<int>> a) {
memset(ans, -1, sizeof(ans));
ll n = a.size();
ll m = a[0].size();
vector<array<ll, 3>> tep;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
tep.pb({a[i][j], i, j});
}
}
sort(tep.begin(), tep.end());
ll sum=0;
for(ll rep=0;rep<n*m/2;rep++){
sum-=tep[rep][0];
v[tep[rep][1]][0].pb(tep[rep][2]);
}
for(ll rep=n*m/2;rep<n*m;rep++){
sum+=tep[rep][0];
v[tep[rep][1]][1].pb(tep[rep][2]);
}
vector<array<ll, 2>> pq;
for(ll rep=0;rep<k;rep++){
pq.clear();
for(ll i=0;i<n;i++){
pq.pb({(ll) v[i][0].size(), i});
}
sort(pq.begin(), pq.end(), greater<array<ll, 2>>());
for(ll i=0;i<n/2;i++){
ll cur=v[pq[i][1]][0].back();
v[pq[i][1]][0].pop_back();
ans[pq[i][1]][cur]=rep;
}
for(ll i=n/2;i<n;i++){
ll cur=v[pq[i][1]][1].back();
v[pq[i][1]][1].pop_back();
ans[pq[i][1]][cur]=rep;
}
}
vector<vector<int>> re(n, vector<int>(m));
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
re[i][j]=(int) ans[i][j];
}
}
allocate_tickets(re);
return sum;
}
