#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "tickets.h"
ll find_maximum(int K, vector<vector<int>> a_given) {
int N = a_given.size();
int M = a_given[0].size();
vector<vi> a(N, vi(M, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
a[i][j] = a_given[i][j];
}
}
vi fc(N, 0); // number of + in row i
// [0, K - 1 - fc[i]] are -, [N - fc[i], N - 1] are +
priority_queue<ii, vector<ii>> pq;
// {gain, pos}
for (int i = 0; i < N; i++) {
pq.push({a[i][K - 1] + a[i][M - 1], i});
}
ll total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
total -= a[i][j];
}
}
for (int i = 0; i < (N * K) / 2; i++) {
// cout<<"at "<<i<<endl;
ll add = pq.top().fi;
int pos = pq.top().se;
pq.pop();
total += add;
fc[pos]++;
if (fc[pos] < K)
pq.push({a[pos][K - 1 - fc[pos]] + a[pos][M - 1 - fc[pos]], pos});
}
/* cout<<"total: "<<total<<endl;
cout<<"fc: ";
for (int i = 0; i < N; i++) {
cout<<fc[i]<<" ";
}
cout<<endl;*/
set<ii> cntp; // current count of plus
// stores {count plus, pos}
for (int i = 0; i < N; i++) {
cntp.insert({fc[i], i});
}
/* cout<<"cntp: "<<endl;
for (ii p : cntp)
cout<<p.fi<<", "<<p.se<<endl;*/
vi cut1(N, M - 1);
vi cut2(N, 0);
vector<vector<int>> answer(N, vector<int>(M, -1));
for (int i = 0; i < K; i++) {
// cout<<"at "<<i<<endl;
auto it = --cntp.end();
set<ii> cntpn; // new count plus
for (int j = 0; j < N / 2; j++) { // use plus
ii curr = *it;
// cout<<"have "<<curr.se<<", "<<cut1[curr.se]<<endl;
answer[curr.se][cut1[curr.se]] = i;
cut1[curr.se]--;
cntpn.insert({curr.fi - 1, curr.se});
it--;
}
for (int j = 0; j < N / 2; j++) { // use minus
ii curr = *it;
// cout<<"have "<<curr.se<<", "<<cut2[curr.se]<<endl;
answer[curr.se][cut2[curr.se]] = i;
cut2[curr.se]++;
cntpn.insert(curr);
it--;
}
cntp = cntpn;
/* cout<<"cntp: "<<endl;
for (ii p : cntp)
cout<<p.fi<<", "<<p.se<<endl;*/
}
allocate_tickets(answer);
return total;
}
