// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
#include "tickets.h"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 15e2 + 5;
const int K = 1e2 + 5;
const int LG = 20;
const int INF = 1e9 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;
int n, m, k, le[N], ri[N], need = 0, cnt[N], i, c, id[N];
long long ans;
set<pair<int, int>> st1, st2;
vector<vector<int>> res;
long long find_maximum(int k, vector<vector<int>> v)
{
n = v.size();
m = v[0].size();
need = k * (n / 2);
ans = 0;
for (int x = 0; x < n; x++)
{
le[x] = 0;
int i = 0;
while (need && i < k)
{
need--;
ans -= v[x][i];
i++;
}
cnt[x] += i;
le[x] += i;
}
need = k * (n / 2);
for (int x = n - 1; x >= 0; x--)
{
ri[x] = m - 1;
int i = 0;
while (need && i < k)
{
need--;
ans += v[x][m - 1 - i];
i++;
}
cnt[x] += i;
ri[x] -= i;
}
for (int x = 0; x < n; x++)
{
if (le[x] > 0)
{
st1.insert({v[x][ri[x]] + v[x][le[x] - 1], x});
}
if (ri[x] < m - 1)
{
st2.insert({v[x][ri[x] + 1] + v[x][le[x]], x});
// cout << v[x][ri[x] + 1] + v[x][le[x]] << " " << x << "v\n";
}
}
while (true)
{
if (st1.empty() || st2.empty())
break;
auto it1 = prev(st1.end());
auto it2 = st2.begin();
if (it1->second == it2->second)
{
// cout << it1->first << " " << it2->first << "\n";
pair<int, int> mx = {-1, 0};
if (st1.size() > 2)
{
mx = max(pair<int, int>{prev(it1)->first - it2->first, 1}, mx);
}
if (st2.size() > 2)
{
mx = max(pair<int, int>{it1->first - next(it2)->first, 2}, mx);
}
if (mx.first <= 0)
{
break;
}
else
{
if (mx.second == 1)
{
it1--;
}
else
{
it2++;
}
}
}
if (it1->first > it2->first)
{
ans += it1->first - it2->first;
int i = it1->second, j = it2->second;
ri[i]--;
le[i]--;
if (le[i] > 0)
{
st1.insert({v[i][ri[i]] + v[i][le[i] - 1], i});
}
ri[j]++;
le[j]++;
if (ri[j] < m - 1)
{
st2.insert({v[j][ri[j] + 1] + v[j][le[j]], j});
}
st1.erase(it1);
st2.erase(it2);
}
else
{
break;
}
}
res.assign(n, vector<int>(m, -1));
for (int x = 0; x < k; x++)
{
cnt[x] = 0;
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < le[x]; y++)
{
while (cnt[id[x]] == (n / 2))
id[x]++;
res[x][y] = id[x];
cnt[id[x]]++;
id[x]++;
}
}
for (int x = 0; x < k; x++)
{
cnt[x] = 0;
}
for (int x = 0; x < n; x++)
{
for (int y = ri[x] + 1; y < m; y++)
{
while (cnt[id[x]] == (n / 2))
id[x]++;
res[x][y] = id[x];
cnt[id[x]]++;
id[x]++;
}
}
allocate_tickets(res);
// for (int x = 0; x < n; x++)
// {
// for (int y = 0; y < m; y++)
// {
// cout << res[x][y] << " ";
// }
// cout << "\n";
// }
return ans;
}
