#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair <int, int> pii;
const int N = 1504;
vector <int> w[N];
int c[N], c2[N];
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;
for (int i = 0; i < n; i++) {
c2[i] = k;
std::vector<int> row(m);
for (int j = 0; j < m; j++)
row[j] = -1;
answer.push_back(row);
}
long long ans = 0;
vector <pair <long long, int>> v;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans += x[i][m - j - 1];
v.push_back(make_pair (x[i][m - j - 1] + x[i][k - j - 1], i));
}
}
sort (v.begin(), v.end());
for (int i = 0; i < (n / 2) * k; i++) {
ans -= v[i].F;
c[v[i].S]++;
c2[v[i].S]--;
}
for (int i = 0; i < k; i++) {
vector <pii> p;
for (int j = 0; j < n; j++) {
p.push_back(make_pair (c[j], j));
}
sort (p.begin(), p.end());
reverse (p.begin(), p.end());
for (int j = 0; j < n / 2; j++) {
c[p[j].S]--;
answer [p[j].S][c[p[j].S]] = i;
}
}
for (int i = 0; i < n; i++) {
set <int> st;
for (int j = 0; j < k; j++)
st.insert (j);
for (int j = 0; j < m; j++) {
if (j >= (m - c2[i])) {
answer[i][j] = (*st.begin());
}
st.erase (answer[i][j]);
}
}
allocate_tickets(answer);
return ans;
}
