#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
long long find_maximum(int k, vector<vector<int> > x)
{
int n = x.size();
int m = x[0].size();
vector<vector<int> > ans;
for (int i = 0; i < n; i++)
{
vector<int> row(m);
for (int j = 0; j < m; j++)
{
row[j] = -1;
}
ans.push_back(row);
}
ll tans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < k; ++j)
{
tans -= x[i][j];
}
}
set<pair<int, int> > s;
vector<int> u;
for (int i = 0; i < n; ++i)
{
u.push_back(k - 1);
s.insert(m_p(x[i][k - 1] + x[i][m - 1], i));
}
for (int ii = 0; ii < n * k / 2; ++ii)
{
int i = (--s.end())->se;
s.erase(--s.end());
tans += (x[i][u[i]] + x[i][m - (k - u[i])]);
--u[i];
if (u[i] >= 0)
s.insert(m_p(x[i][u[i]] + x[i][m - (k - u[i])], i));
}
vector<int> l, r;
for (int i = 0; i < n; ++i)
{
l.push_back(u[i]);
r.push_back(m - (k - u[i]) + 1);
}
for (int ii = 0; ii < k; ++ii)
{
vector<int> v;
int q1 = 0;
int q2 = 0;
for (int i = 0; i < n; ++i)
{
if (l[i] == -1)
{
ans[i][r[i]++] = ii;
++q1;
}
else if (r[i] == m)
{
ans[i][l[i]--] = ii;
++q2;
}
else
{
v.push_back(i);
}
}
for (int i = 0; i < (n / 2) - q1; ++i)
{
ans[v[i]][r[v[i]]++] = ii;
}
for (int i = (n / 2) - q1; i < sz(v); ++i)
{
ans[v[i]][l[v[i]]--] = ii;
}
}
allocate_tickets(ans);
return tans;
}
