#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
int mn[MAXN], mx[MAXN];
long long dp[MAXN][MAXN];
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
vector<vector<int>> ans(n);
vector<vector<int>> v(m);
for (int i = 0; i < n; i++) {
ans[i].resize(m);
for (int j = 0; j < m; j++){
if(i < n/2)ans[i][j] = j;
else ans[i][j] = m-j-1;
v[ ans[i][j] ].push_back(x[i][j]);
}
}
long long resp = 0;
for(int j = 0; j < m; j++){
sort(v[j].begin(),v[j].end());
for(int i = 0; i < n/2; i++)resp -= v[j][i];
for(int i = n/2; i < n; i++)resp += v[j][i];
}
allocate_tickets(ans);
return resp;
}
