#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<lint,lint> ii;
int taken[1505];
bool takelow[1505][1505];
bool takehigh[1505][1505];
vector<int> small[1505];
vector<int> big[1505];
vector<vector<int>> arr;
int n, m;
long long find_maximum(int k, vector<vector<int>> ARR){
arr = ARR;
n = arr.size(), m = arr[0].size();
vector<vector<int>> answer;
lint ans = 0;
for(int i = 0;i < n;i++){
std::vector<int> row(m);
fill(all(row), -1);
answer.push_back(row);
}
for(int i = 0;i < n;i++){
for(int j = 0;j < k;j++){
ans -= arr[i][j];
takelow[i][j] = true;
}
}
priority_queue<ii> pq;
for(int color = 0;color < n;color++){
int t = taken[color];
lint low = arr[color][k-t-1];
lint high = arr[color][m-t-1];
pq.push(ii(low+high, color));
}
for(int turn = 0;turn < n*k/2;turn++){
ii T = pq.top(); pq.pop();
ans += T.first;
int color = T.second;
int t = taken[color];
takelow[color][k-t-1] = false;
takehigh[color][m-t-1] = true;
taken[color]++;
///push stuff into pq
t = taken[color];
if(t != k){
lint low = arr[color][k-t-1];
lint high = arr[color][m-t-1];
pq.push(ii(low+high, color));
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(takelow[i][j]) small[i].push_back(j);
if(takehigh[i][j]) big[i].push_back(j);
}
}
for(int turn = 0;turn < k;turn++){
int needBig = n/2;
bool taken[n]; fill(taken, taken+n, false);
for(int i = 0;i < n;i++){
if(sz(big[i]) == 0){
int p = small[i].back(); small[i].pop_back();
answer[i][p] = turn;
taken[i] = true;
}
else if(sz(small[i]) == 0){
int p = big[i].back(); big[i].pop_back();
answer[i][p] = turn;
needBig--;
taken[i] = true;
}
}
for(int i = 0;i < n;i++){
if(taken[i]) continue;
if(needBig != 0){
int p = big[i].back(); big[i].pop_back();
answer[i][p] = turn;
needBig--;
}
else{
int p = small[i].back(); small[i].pop_back();
answer[i][p] = turn;
}
}
}
allocate_tickets(answer);
return ans;
}
