///
/// 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;
set<pll> s[N];
int n, m;
vector<vector<int>> ans;
//void allocate_tickets(vector<vector<int>> s){}
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));
Loop(i,0,n) Loop(j,0,m)
s[i].insert({x[i][j], j});
ll fans = 0;
Loop(_,0,k){
vector<pll> vec(n);
Loop(i,0,n) vec[i] = {s[i].begin()->first + (--s[i].end())->first, i};
sort(vec.begin(), vec.end());
Loop(ii,0,n/2){
int i = vec[ii].second;
int j = s[i].begin()->second;
s[i].erase({x[i][j], j});
fans -= x[i][j];
ans[i][j] = _;
}
Loop(ii,n/2,n){
int i = vec[ii].second;
int j = (--s[i].end())->second;
s[i].erase({x[i][j], j});
fans += x[i][j];
ans[i][j] = _;
}
}
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';
// }
//}
