#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 2010;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int LOG = 20;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int n, m, k;
int a[1510][1510], num[MAXN], oth[MAXN], l[MAXN], r[MAXN];
int las[MAXN], ty[MAXN][MAXN], tag[MAXN];
long long find_maximum(int K, std::vector<std::vector<int>> x) {
n = x.size(); m = x[0].size(); k = K;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) a[i][j] = x[i][j];
}
vector<array<int,3>> vec;
ll val = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
val -= x[i][j];
vec.pb({x[i][j]+x[i][j], i, j});
}
}
sort(vec.rbegin(), vec.rend());
vector<int> RET(m, -1);
vector<vector<int>> ans(n, RET);
for(int i=0; i<n; i++) oth[i] = m;
for(int i=0; i<n*m/2; i++){
val += vec[i][0];
ty[vec[i][1]][vec[i][2]] = 1;
num[vec[i][1]]++;
oth[vec[i][1]]--;
}
// for(int i=0; i<n; i++){
// for(int j=0; j<m; j++){
// cout << ty[i][j] << " \n"[j==m-1];
// }
// }
priority_queue<pii> pq;
for(int i=0; i<n; i++){
pq.push({num[i], i});
r[i] = m-1; l[i] = 0;
}
int day = 0;
for(int i=0; i<k; i++){
// ambil n/2 terkecil
day++;
// cout << i << " i\n";
for(int j=0; j<n/2; j++){
auto [v, idx] = pq.top(); pq.pop();
// cout << idx << ' ';
tag[idx] = day;
}
// cout << " idx yg kena\n";
for(int in=0; in<n; in++){
if(tag[in] == day){
ans[in][r[in]] = i;
r[in]--;
num[in]--;
if(num[in] != 0) pq.push({num[in], in});
} else {
ans[in][l[in]] = i;
l[in]++;
}
}
}
allocate_tickets(ans);
return val;
}
