///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#include "tickets.h"
const int N = 1510;
vector<vector<int>> ans;
int cnt[N], ccnt[N];
int n, m;
//void allocate_tickets(vector<vector<int>> s){}
//int npl(int _, int i){
// return n-cnt[i]+ccnt[i];
//}
//int nmi(int _, int i){
// return _-ccnt[i];
//}
ll find_maximum(int k, vector<vector<int>> x)
{
n = x.size(); m = x[0].size();
ans = vector<vector<int>>(n, vector<int>(m, -1));
vector<pll> vec;
ll fans = 0;
Loop(i,0,n){
Loop(j,0,k) {
fans -= x[i][j];
vec.push_back({x[i][j] + x[i][m+j-k], i});
}
}
sort(vec.begin(), vec.end(), greater<pll>());
Loop(i,0,n*k/2){
cnt[vec[i].second]++;
fans += vec[i].first;
}
Loop(_,0,k){
int sum=0;
Loop(i,0,n){
if(cnt[i] == ccnt[i])
ans[i][_-cnt[i]] = _, --sum;
else if(_-ccnt[i] == k-cnt[i])
ans[i][m-cnt[i]+ccnt[i]] = _, ++sum, ++ccnt[i];
else if(sum > 0)
ans[i][_-cnt[i]] = _, --sum;
else
ans[i][m-cnt[i]+ccnt[i]] = _, ++sum, ++ccnt[i];
}
assert(sum == 0);
}
allocate_tickets(ans);
return fans;
}
//int main(){
// cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << '\n';
// Loop(i,0,n){
// Loop(j,0,m) cout << ans[i][j] << ' ';
// cout << '\n';
// }
//}
