#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
struct el {
long long x, y, idx;
bool operator < (const el &oth) const {
return (x - y) < (oth.x - oth.y);
}
};
bool comp (pair <long, long> a, pair <long, long> b) {
return (a.first - b.second) > (b.first - b.second);
}
long long find_maximum(int k, vector<vector<int>> x) {
long long n = x.size();
long long m = x[0].size();
if (m == 1){ // subtask 1
vector<vector<int>> answer (n, vector <int> (m));
long long rs = 0;
vector <int> v;
for (int i = 0; i < n; i++){
v.push_back(x[i][0]);
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++){
rs+=abs(x[i][0] - v[n / 2]);
}
allocate_tickets(answer);
return rs;
}
else if (k == 1) { // subtask 2
vector<vector<int>> answer (n, vector <int> (m, -1));
vector <int> is (n);
long long rs = 0, med = 0, wh = 0, whj = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
// vector <int> tis (n);
long long trs = 0;
int low = 0;
vector <el > v;
for (int k = 0; k < n; k++){
if (i == k) continue;
if (x[k][m-1] < x[i][j]) {
low++;
trs+=x[i][j] - x[k][0];
}
else if (x[k][0] > x[i][j]) {
trs+=x[k][m-1] - x[i][j];
}
else {
v.push_back({x[i][j] - x[k][0], x[k][m-1] - x[i][j], k});
}
}
if (low >= n / 2) continue;
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (auto now: v) {
assert(now.x >= 0 && now.y >= 0);
if (low != n / 2 - 1) {
trs+=now.x;
low++;
}
else {
trs+=now.y;
}
}
if (trs > rs && low == n / 2 - 1) {
rs = trs;
med = x[i][j];
wh = i;
whj = j;
}
}
}
answer[wh][whj] = 0;
int low = 0;
vector <el > v;
for (int k = 0; k < n; k++){
if (wh == k) continue;
if (x[k][m-1] < med) {
low++;
answer[k][0] = 0;
}
else if (x[k][0] > med) {
answer[k][m-1] = 0;
}
else {
v.push_back({med - x[k][0], x[k][m-1] - med, k});
}
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (auto now: v) {
assert(now.x >= 0 && now.y >= 0);
if (low != n / 2 - 1) {
answer[now.idx][0] = 0;
low++;
}
else {
answer[now.idx][m-1] = 0;
}
}
allocate_tickets(answer);
return rs;
}
else { // subtask 3
// int n0 = 0, n1 = 0;
// for (int i = 0; i < n; i++){
// for (int j = 0; j < m; j++){
// n0+=x[i][j] == 0;
// n1+=x[i][j] == 1;
// }
// }
// for (int i = 0; i < k; i++){
// }
}
return -1;
}
