#include "tickets.h"
#include <bits/stdc++.h>
#include <vector>
#define pb push_back
using namespace std;
int big[2002];
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer;
if(m == 1)
{
long long b;
vector < long long > g;
for (int i = 0; i < n; ++ i)
g.pb(1LL * x[i][0]);
sort(g.begin(), g.end());
long long half1 = g[n/2];
for (int i = 0; i < n; i++)
{
std::vector<int> row(m);
for (int j = 0; j < m; j++)
{
row[j] = 0;
/*if (j < k)
{
row[j] = j;
}
else
{
row[j] = -1;
}*/
}
answer.push_back(row);
}
allocate_tickets(answer);
long long ans = 0;
for (auto x: g)
ans += 1LL * abs(x - half1);
return ans;
}
for (int i = 0; i < n; i++)
{
std::vector<int> row(m);
for (int j = 0; j < m; j++)
{
row[j] = -1;
}
answer.push_back(row);
}
int fh = (n-2)/2, sh = (n-2)/2 + 1;
long long sum = 0;
vector < pair < long long, long long > > g;
for (int i = 0; i < n; ++ i)
{
big[i] = 1;
sum += x[i][m-1];
g.pb(make_pair(x[i][m-1] + x[i][0], i));
}
sort(g.begin(), g.end());
for (int i = 0; i < n/2; ++ i)
{
sum -= g[i].first;
big[g[i].second] = 0;
}
for (int i = 0; i < n; ++ i)
{
if(big[i])answer[i][m-1] = 0;
else answer[i][0] = 0;
}
allocate_tickets(answer);
return sum;
}
