#include <bits/stdc++.h>
#include "tickets.h"
//#include "grader.cpp"
using namespace std ;
const int MAX = 1500 + 10 ;
int cnt[MAX] ;
long long find_maximum(int k, std::vector<std::vector<int>> v)
{
int n = v.size() , m = v[0].size() ;
long long ans = 0 ;
vector< array<int , 3> >v2 ;
vector< vector<int> >alo = vector< vector<int> >(n , vector<int>(m , 0)) ;
for(int i = 0 ; i < n ; ++i)
{
for(int j = m-1 ; j > m-1-k ; --j)
ans += v[i][j] , alo[i][j] = 1 ;
for(int j = 0 ; j < k ; ++j)
v2.push_back({v[i][j] + v[i][m-1-k+1+j] , i , j}) ;
}
sort(v2.begin() , v2.end()) ;
int taken = 0 ;
for(auto &p : v2)
{
if(taken == n*k/2)
break ;
if(cnt[p[1]] == k)
continue ;
taken++ ;
ans -= p[0] ;
cnt[p[1]]++ ;
alo[p[1]][p[2]] = -1 , alo[p[1]][m-1-k+1+p[2]] = 0 ;
}
allocate_tickets(alo) ;
return ans ;
}
