#include "tickets.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define F first
#define S second
#define PB push_back
using ll = long long;
// each vector<int> in x is sorted
long long find_maximum(int k, vector<vector<int>> x) {
/* sample interaction
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
if (j < k) {
row[j] = j;
} else {
row[j] = -1;
}
}
answer.push_back(row);
}
allocate_tickets(answer);
return 1;
*/
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
// same sol as subtask 2 but all values all at once
ll sum = 0;
struct Info {
int val;
int i, j, k;
bool operator<(const Info &rhs) const {
return val < rhs.val;
}
};
priority_queue<Info> pq;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
answer[i][j] = -2; // lower half
int jj = m-k+j;
sum -= x[i][j];
pq.push({x[i][j]+x[i][jj], i, j, jj});
}
}
for(int i = 0; i < k*n/2; i++) {
answer[pq.top().i][pq.top().j] = -1;
answer[pq.top().i][pq.top().k] = -3; // upper half
sum += pq.top().val;
pq.pop();
}
vector<vector<int>> lo(n), up(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(answer[i][j] == -2) {
lo[i].PB(j);
}
else if(answer[i][j] == -3) {
up[i].PB(j);
}
}
}
for(int q = 0; q < k; q++) {
int cnt = n/2;
vector<bool> skip(n);
for(int i = 0; i < n && cnt; i++) {
if(lo[i].size()) {
skip[i] = true;
answer[i][lo[i].back()] = q;
lo[i].pop_back();
cnt--;
}
}
for(int i = 0; i < n; i++) {
if(!skip[i] && up[i].size()) {
answer[i][up[i].back()] = q;
up[i].pop_back();
}
}
}
allocate_tickets(answer);
return sum;
}
