#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] , c[maxn][maxn] , id[maxn] ;
vector <pii> b[maxn] ;
long long find_maximum(int k, vector< vector<int>> aa) {
n = sz(aa) ;
m = sz(aa[0]) ;
rep(i ,0 , n-1){
rep(j , 0 ,m-1){
a[i][j] = aa[i][j] ;
b[i].pb({a[i][j] , j}) ;
c[i][j] = -1 ;
}
sort(all(b[i])) ;
}
ll sm =0 ;
rep(i ,1, k){
vector <pii> az ;
rep(i ,0 , n-1){
sm += b[i].back().F ;
az.pb({+b[i].back().F+b[i][id[i]].F , i}) ;
}
sort(all(az)) ;
rep(j , 0 ,n/2-1){
int x= az[j].S ;
c[x][b[x][id[x]].S] = i-1 ;
id[x]++;
sm -= az[j].F ;
}
rep(j , n/2 , n-1){
int x = az[j].S;
c[x][b[x].back().S] = i-1 ;
b[x].pop_back() ;
}
}
vector < vector <int> > vec ;
rep(i , 0 , n-1){
vector <int> f ;
rep(j , 0, m-1){
f.pb(c[i][j]) ;
}
vec.pb(f) ;
}
allocate_tickets(vec) ;
return sm;
}
