//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 5001
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
void allocate_tickets(vector<vector<int> > s);
//void allocate_tickets(vector<vector<int> > s){
// for(vector<int>& v : s){
// for(int x : v){
// cout << x << ' ';
// }
// cout << endl;
// }
// cout << endl;
// return;
//}
ll find_maximum(int k, vector<vector<int> > x){
int n = x.size();
int m = x[0].size();
int U[n], L[n];
pair<int, int> rows[n];//delta, id
for(int i=0;i<n;++i){
int lo = x[i][0];
int hi = x[i][0];
U[i] = 0;
L[i] = 0;
for(int j=1;j<m;++j){
if(x[i][j] < lo){
L[i] = j;
lo = x[i][j];
}
if(x[i][j] > hi){
U[i] = j;
hi = x[i][j];
}
}
rows[i] = {lo+hi, i};
}
sort(rows, rows+n);
reverse(rows, rows+n);
vector<vector<int> > ans;
for(int i=0;i<n;++i){
vector<int> tmp;
for(int j=0;j<m;++j){
tmp.pb(-1);
}
ans.pb(tmp);
}
ll res = 0ll;
for(int i=0;i<n/2;++i){
int id = rows[i].se;
ans[id][U[id]] = 0;
res += x[id][U[id]];
}
for(int i=(n/2);i<n;++i){
int id = rows[i].se;
ans[id][L[id]] = 0;
res -= x[id][L[id]];
}
allocate_tickets(ans);
return res;
}
