#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2000 + 10 , sq = 333 , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 7 ;
int n , m , a[maxn][maxn] , t[maxn] , c[maxn][maxn] , id[maxn] , c2[maxn][maxn] ;
vector <pii> b[maxn] ;
long long find_maximum(int k, vector< vector<int>> aa) {
n = sz(aa) ;
m = sz(aa[0]) ;
vector <pair<int,pii> > vec ;
rep(i ,0 , n-1){
rep(j , 0 ,m-1){
a[i][j] = aa[i][j] ;
c[i][j] = -1 ;
c2[i][j] = 0 ;
vec.pb({a[i][j] , {i,j}}) ;
}
}
sort(all(vec)) ;
int f = n*k/2 , sm =0 ;
per(i , sz(vec)-1 , 0){
int x = vec[i].S.F , y = vec[i].S.S ;
if(t[x] == k)continue ;
f--;
t[x]++ ;
c2[x][y] =1 ;
sm += a[x][y] ;
if(f==0)break ;
}
f = n*k/2 ;
rep(i ,0 , sz(vec)-1){
int x = vec[i].S.F , y = vec[i].S.S ;
if(t[x] == k)continue ;
f--;
t[x]++;
c2[x][y] = -1 ;
sm -= a[x][y] ;
if(f==0)break;
}
rep(j , 0 ,k)t[j] = 0;
rep(i ,0 , n-1){
vector <int> f , f2 ;
rep(j , 0 ,m-1){
if(c2[i][j] == 1)
f.pb(j) ;
if(c2[i][j] == -1)
f2.pb(j) ;
}
vector <pii> az ;
rep(j , 0 , k-1){
az.pb({t[j],j});
}
sort(all(az)) ;
rep(j , 0 ,sz(f)-1){
c[i][f[j]]= az[j].S ;
t[az[j].S]++ ;
}
rep(j , 0, sz(f2)-1){
c[i][f2[j]] = az[j+sz(f)].S ;
}
}
vector <vector <int> > vec2 ;
rep(i , 0 , n-1){
vector <int> f ;
rep(j , 0, m-1){
f.pb(c[i][j]) ;
}
vec2.pb(f) ;
}
allocate_tickets(vec2) ;
return sm;
}
