// Problem: P3 - Carnival Tickets
// Contest: DMOJ - IOI '20
// URL: https://dmoj.ca/problem/ioi20p3
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include "tickets.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long find_maximum(int k, vector<vector<int>> V)
{
int n = V.size();
int m = V[0].size();
vector<vector<array<lg, 2>>> v;
lg ans = 0;
vector<array<lg, 4>> o;
auto a = V;
for(int i = 0; i < n; i++)
{
v.push_back({});
for(int j = 0; j < m; j++)
{
v[i].push_back({V[i][j], j});
a[i][j] = -1;
}
}
vector<int> neg[n], pos[n];
for(int i = 0; i < n; i++)
{
sort(v[i].begin(), v[i].end());
for(int j = 0; j < k; j++)
{
ans -= v[i][j][0];
o.push_back({v[i][m-k+j][0]+v[i][j][0], i, v[i][j][1], v[i][m-k+j][1]});
}
}
vector<array<int, 2>> npos(n);
for(int i = 0; i < n; i++) npos[i] = {0, i};
sort(o.rbegin(), o.rend());
for(int i = 0; i < n*k/2; i++)
{
ans += o[i][0];
pos[o[i][1]].push_back(o[i][3]);
npos[o[i][1]][0]++;
}
for(int i = n*k/2; i < n*k; i++)
{
neg[o[i][1]].push_back(o[i][2]);
}
for(int i = 0; i < k; i++)
{
sort(npos.begin(), npos.end());
//negatives
for(int j = 0; j < n/2; j++)
{
a[npos[j][1]][neg[npos[j][1]].back()] = i;
neg[npos[j][1]].pop_back();
}
//positives
for(int j = n/2; j < n; j++)
{
a[npos[j][1]][pos[npos[j][1]].back()] = i;
pos[npos[j][1]].pop_back();
npos[j][0]--;
}
}
allocate_tickets(a);
return ans;
}
