#include <bits/stdc++.h>
using namespace std;
#include "tickets.h"
typedef long long ll;
#define F first
#define S second
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 1505;
int tk[N], n, m, k;
vector<vector<int>> a;
vector<int> vv[N], vv2[N];
ll gt(int id) {
if (tk[id] == k)return 1e18;
return (a[id][k-1-tk[id]] + a[id][m-1-tk[id]]);
}
ll find_maximum(int ko, vector<vector<int>> xx) {
a = xx;
n = sz(a);
m = sz(a[0]);
k = ko;
a = xx;
ll ans = 0;
set<pair<ll, int>> s;
for (int i = 0; i < n; i++) {
tk[i] = 0;
vv[i].clear();
vv2[i].clear();
sort(all(a[i]), greater<>());
for (int j = 0; j < k; j++) {
ans += a[i][j];
}
s.insert({gt(i), i});
}
int cnt = (n >> 1) * k;
while (cnt--) {
ll x = s.begin()->F;
int i = s.begin()->S;
s.erase(s.begin());
ans -= x;
++tk[i];
s.insert({gt(i), i});
}
vector<vector<int>> res(n, vector<int> (m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k-1-tk[i]; j++) {
vv[i].pb(j);
}
for (int j = m-1; j > m-1-tk[i]; j--) {
vv2[i].pb(j);
}
}
for (int ii = 0; ii < k; ii++) {
vector<pair<int, int>> vo;
for (int i = 0; i < n; i++)vo.pb({sz(vv[i]), i});
sort(all(vo));
for (int i = 0; i < n; i++) {
int cur = vo[i].S;
if (vv[cur].empty() || (i < n/2 && !vv2[cur].empty())) {
res[cur][vv2[cur].back()] = ii;
vv2[cur].pop_back();
} else {
res[cur][vv[cur].back()] = ii;
vv[cur].pop_back();
}
}
}
allocate_tickets(res);
return ans;
}
/*int main() {
int nn, mm, kk;
cin >> nn >> mm >> kk;
vector<vector<int>> vvv(nn, vector<int>(mm));
for (int i = 0; i < nn; i++) {
for (int j = 0; j < mm; j++) {
cin >> vvv[i][j];
}
}
cout << find_maximum(kk, vvv);
}*/
