#include "tickets.h"
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
int a[1505][1505], viz[1505][1505];
struct str{
int val, x, y;
};
str w[1501 * 1501];
int cmp(str a, str b){
return a.val < b.val;
}
int cmp2(str a, str b){
return a.x < b.x;
}
long long find_maximum(int k, vector< vector<int> > x) {
int n, m, i, j, nr, jj, u;
long long sol = 0;
n = x.size();
m = x[0].size();
nr = 0;
for(i = 0; i < n; i++){
jj = 0;
for(j = m - k; j < m; j++){
sol += x[i][j];
w[++nr] = {x[i][j] + x[i][jj], i, jj};
jj++;
}
}
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
a[i][j] = -1;
}
}
sort(w + 1, w + nr + 1, cmp);
nr /= 2;
sort(w + 1, w + nr + 1, cmp2);
j = 0;
for(i = 1; i <= nr; i++){
sol -= w[i].val;
a[ w[i].x ][ w[i].y ] = j;
viz[ w[i].x ][j] = 1;
j++;
if(j == k){
j = 0;
}
}
for(i = 0; i < n; i++){
u = 0;
for(j = m - 1; j >= 0; j--){
if(a[i][j] != -1){
continue;
}
while(viz[i][u] == 1){
u++;
}
if(u == k){
break;
}
viz[i][u] = 1;
a[i][j] = u;
}
}
vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = a[i][j];
}
answer.push_back(row);
}
allocate_tickets(answer);
return sol;
}
