#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>
#define N 1505
using namespace std;
int n, m, k, cnt = 0, low[N], high[N], used[N];
vector<vector<int>> answer, a;
long long int total = 0;
struct Dat {
long long int sum;
int col, pos;
Dat(){}
Dat(long long int s, int c, int p) {
sum = s;
col = c;
pos = p;
}
bool operator < (const Dat &d) {
return sum < d.sum;
}
} D[N * N];
vector<pair<int, int>> small, large;
void prepDat() {
for (int i=0; i<n; i++) {
for (int j=0; j<k; j++) {
D[cnt++] = Dat(a[i][j] + a[i][m-k+j], i, j);
}
}
}
void generateAnswer() {
for (int i=0; i<n; i++) low[i] = 0;
for (int i=0; i<cnt/2; i++)
low[D[i].col] = max(low[D[i].col], D[i].pos + 1);
for (int i=0; i<n; i++) high[i] = k - low[i];
small.clear(); large.clear();
for (int i=0; i<n; i++) if (low[i] > 0) small.push_back(make_pair(low[i], i));
for (int i=0; i<n; i++) if (high[i] > 0) large.push_back(make_pair(high[i], i));
for (int i=0; i<n; i++) {
vector<int> row(m, -1);
answer.push_back(row);
//printf("[%d] %d %d\n", i, low[i], high[i]);
}
sort(small.begin(), small.end(), greater<pair<int, int>>());
sort(large.begin(), large.end(), greater<pair<int, int>>());
for (int i=0; i<k; i++) {
for (int j=0; j<n; j++) used[j] = 0;
int x = 0, y = 0;
for (int j=0; j<n/2; j++) {
while (used[small[x].second] && x < small.size()) x++;
if (x == small.size()) while (true) {}
used[small[x].second] = 1;
while (used[large[y].second] && y < large.size()) y++;
if (y == large.size()) while (true) {a[n * 1000][0] = 1;}
used[large[y].second] = 1;
int c1 = small[x].second, c2 = large[y].second;
int p1 = small[x].first - 1, p2 = m - large[y].first;
//printf("[%d %d], [%d %d]\n", c1, p1, c2, p2);
answer[c1][p1] = i;
answer[c2][p2] = i;
total += a[c2][p2] - a[c1][p1];
low[c1]--;
high[c2]--;
}
small.clear();
large.clear();
for (int j=0; j<n; j++) if (low[j] > 0) small.push_back(make_pair(low[j], j));
for (int j=0; j<n; j++) if (high[j] > 0) large.push_back(make_pair(high[j], j));
sort(small.begin(), small.end(), greater<pair<int, int>>());
sort(large.begin(), large.end(), greater<pair<int, int>>());
}
}
long long find_maximum(int K, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
k = K;
a = x;
prepDat();
sort(D, D + cnt);
generateAnswer();
allocate_tickets(answer);
return total;
}
