#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;
#define ST first
#define ND second
#define PB push_back
const int nax = 1500 + 10;
int take[nax];
void allocate_tickets(vector<vi> a);
ll find_maximum(int k, vector<vi>x) {
int n = (int)x.size();
int m = (int)x[0].size();
ll ans = 0;
for(int i = 0; i < k; ++i) {
for(int j = 0; j < n; ++j) {
ans -= x[j][i];
}
}
priority_queue<pi>PQ;
for(int i = 0; i < n; ++i) {
take[i] = 0;
PQ.push({x[i][m - 1] + x[i][k - 1], i});
}
int cur = 0;
while(cur < n * k / 2) {
cur++;
pi tp = PQ.top();
ans += tp.ST;
PQ.pop();
take[tp.ND]++;
if(take[tp.ND] < k) {
PQ.push({x[tp.ND][m - 1 - take[tp.ND]] + x[tp.ND][k - 1 - take[tp.ND]], tp.ND});
}
}
vector<vi>res(n);
for(int i = 0; i < n; ++i) res[i].resize(m, -1);
vector<vector<bool>>t(n);
for(int i = 0; i < n; ++i) t[i].resize(k+1);
for(int turn = k - 1; turn >= 0; --turn) {
cur = 0;
for(int i = 0; i < n; ++i) {
if(take[i] == turn + 1) {
t[i][turn] = 1;
cur++;
continue;
} else if(take[i] == 0) {
t[i][turn] = 0;
cur--;
continue;
}
}
for(int i = 0; i < n; ++i) {
if(take[i] == turn + 1 || take[i] == 0) continue;
if(cur < 0) {
t[i][turn] = 1;
cur++;
} else {
t[i][turn] = 0;
cur--;
}
}
for(int i = 0; i < n; ++i) {
if(t[i][turn]) take[i]--;
}
}
vi l(n, 0);
vi r(n, m-1);
for(int turn = 0; turn < k; ++turn) {
for(int i = 0; i < n; ++i) {
if(t[i][turn]) {
res[i][r[i]--] = turn;
} else {
res[i][l[i]++] = turn;
}
}
}
allocate_tickets(res);
//for(int i = 0; i < n; ++i) {
// for(int j = 0; j < m; ++j) {
// cout << res[i][j] << " ";
// }
// cout << "\n";
//}
return ans;
}
//int main() {
// cout << find_maximum(2, {{0, 2, 5},{1, 1, 3}}) << "\n";
// cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << "\n";
//}
