#include "tickets.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
const ll INF = 1e18;
int n, m, K;
vector<vi> answer;
deque<pair<int,ll>> hi, lo;
void add_element(ll x1, ll x2, int pos){
(x1 == 1)? hi.push_front({x1, pos}) : hi.push_back({x1, pos});
(x2 == 1)? lo.push_back({x2, pos}) : lo.push_front({x2, pos});
}
pair<ll, ii> calc(int& a, int& b, int i){
pair<ll, ii> ret;
while(answer[hi[a].second][m-1] != -1 && a < n) a++;
while(answer[lo[b].second][0] != -1 && b < n) b++;
if(i%2 == 0 && answer[hi[a].second][m-1] == -1){
ret.first = hi[a].first;
ret.second = { hi[a].second, m-1 };
return ret;
}
if(i%2 == 0 || answer[lo[b].second][0] == -1){
ret.first = lo[b].first;
ret.second = { lo[b].second, 0 };
return ret;
}
ret.first = hi[a].first;
ret.second = { hi[a].second, m-1 };
return ret;
}
ll find_maximum(int k, vvi x){
n = x.size();
m = x[0].size();
answer = vvi(n, vi(m, -1));
ll S = 0;
for(int it = 0; it < k; it++){
hi.clear(); lo.clear();
for(int i=0; i<n; i++) add_element(x[i][m-1], x[i][0], i);
int a=0, b=0; ll max_value = -INF, min_value = INF;
vector<ll> selected(n, -1);
for(int i=0; i<n; i++){
pair<ll, pair<int,int>> p = calc(a, b, i);
answer[p.second.first][p.second.second] = it;
selected[i] = p.first;
max_value = max(max_value, p.first);
min_value = min(min_value, p.first);
}
ll s1, s2; s1 = s2 = 0;
ll mid_floor = (max_value + min_value) / 2;
ll mid_ceil = (max_value + min_value + 1) / 2;
for(int i=0; i<n; i++) s1 += abs(selected[i] - mid_floor);
for(int i=0; i<n; i++) s2 += abs(selected[i] - mid_ceil);
S += min(s1, s2);
}
allocate_tickets(answer);
return S;
}
