#include "tickets.h"
#include <vector>
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
long long find_maximum(int k, vector<vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
vector<vector<int> > res(n, vector<int>(m, -1));
vector<int> h(n, 0), l(n, k);
long long sum = 0;
vector<pair<int, int> > st;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
st.emplace_back(x[i][k - j - 1] + x[i][m - j - 1], i);
sum -= x[i][j];
}
}
sort(rall(st));
for (int i = 0; i < n * k / 2; i++) {
sum += st[i].first;
h[st[i].second]++;
l[st[i].second]--;
}
for (int col = 0; col < k; col++) {
int U = n / 2, L = n / 2;
vector<bool> bad(n, false);
for(int i = 0; i < n; i++) {
if (h[i] == 0) {
l[i]--;
res[i][l[i]] = col;
bad[i] = true;
L--;
} else if (l[i] == 0) {
h[i]--;
res[i][m - h[i] - 1] = col;
bad[i] = true;
U--;
}
}
for (int i = 0; i < n; i++) {
if (!bad[i]) {
if (U) {
h[i]--;
res[i][m - h[i] - 1] = col;
bad[i] = true;
U--;
} else {
l[i]--;
res[i][l[i]] = col;
bad[i] = true;
L--;
}
}
}
}
allocate_tickets(res);
return sum;
}
