#include "tickets.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 1505;
struct node{
int x, y, v;
bool operator<(const node &n)const{
return v < n.v;
}
};
void FUCKING_BACKTRACK(vector<vector<int>> B, int k){
deque<int> dq[MAXN];
int bcnt[MAXN] = {};
for(int i=0; i<sz(B); i++){
for(auto &j : B[i]){
if(j > 0) bcnt[i]++;
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == -1) dq[i].push_back(j);
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == +1) dq[i].push_back(j);
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == 0) B[i][j] = -1;
else B[i][j] = 0;
}
}
for(int i = 0; i < k; i++){
vector<int> idx(sz(B));
iota(all(idx), 0);
sort(all(idx), [&](const int &a, const int &b){
return bcnt[a] < bcnt[b];
});
for(int j=0; j<sz(B); j++){
int x = idx[j];
int y = (j < sz(B) / 2 ? dq[x].front() : dq[x].back());
B[x][y] = i;
if(j < sz(B) / 2) dq[x].pop_front();
else{
dq[x].pop_back();
bcnt[x]--;
}
}
}
allocate_tickets(B);
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
vector<vector<int>> B(n);
for(auto &i : B) i.resize(m);
vector<node> v;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
v.push_back({i, j, x[i][j]});
}
}
sort(all(v));
int l = 0, r = sz(v) - 1;
vector<int> cnt(n);
lint ret = 0;
for(int i=0; i<(n/2)*k; i++){
while(cnt[v[l].x] == k) l++;
B[v[l].x][v[l].y] = -1;
ret -= v[l].v;
cnt[v[l].x]++;
while(cnt[v[r].x] == k) r--;
B[v[r].x][v[r].y] = 1;
ret += v[r].v;
cnt[v[r].x]++;
}
FUCKING_BACKTRACK(B, k);
return ret;
}
