#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const int INF = 1e9;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll erkaranun[1507][1507];
ll cnt0[1507];
vector<pair<int, int>>d;
vector<int>os[1507], ls[1507];
int os_[1507], ls_[1507];
vector<vector<int>>ans;
vector<int>ap, am;
vector<vector<int>>a;
bool isap[1507];
bool isam[1507];
bool ismx[1507][1507];
bool ismn[1507][1507];
ll mxc[1507];
ll mnc[1507];
int mxi[1507], mni[1507];
ll dp[1507][1507];
ll DP[307][90007];
struct Ket {
int i, j, val;
Ket(int ii, int jj, int vl) {
i = ii;
j = jj;
val = vl;
}
bool operator<(const Ket& other)const {
return val < other.val;
}
friend ostream& operator<<(ostream& os, Ket val);
};
ostream& operator<<(ostream& os, Ket val) {
os << val.i << " " << val.j << ": " << val.val << "; ";
return os;
}
vector<vector<Ket>>s;
struct Tox{
int pr,sf,ogut,i;
Tox(int ii){
pr=k;
sf=0;
i=ii;
count_ogut();
for(int j=0;j<pr;j++){
ismn[i][s[i][j].j]=true;
}
}
void count_ogut(){
if(pr==0)ogut=-INF;
else ogut=s[i][m-sf-1].val+s[i][pr-1].val;
}
void update(){
ismn[i][s[i][pr-1].j]=false;
ismx[i][s[i][m-sf-1].j]=true;
pr--;
sf++;
count_ogut();
}
bool operator<(const Tox& other)const{
return ogut<other.ogut;
}
};
vector<Ket>sax;
priority_queue<Tox>q;
void give_max(int i, int r) {
////cout << "-- " << i << " " << r << " " << mxc[i] << endl;
mxc[i]--;
for (int j = mxi[i] + 1; j < m; j++) {
if (ismx[i][j]) {
////cout << j << endl;
mxi[i] = j;
ans[i][j] = r;
break;
}
}
}
void give_min(int i, int r) {
////cout << "== " << i << " " << r << endl;
mnc[i]--;
for (int j = mni[i] + 1; j < m; j++) {
if (ismn[i][j]) {
//////cout << j << " ";
mni[i] = j;
ans[i][j] = r;
break;
}
}
}
ll find_maximum(int K, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
a=x;
k=K;
for (int i = 0; i < n; i++) {
vector<Ket>v;
s.push_back(v);
for (int j = 0; j < m; j++) {
Ket ket(i, j, x[i][j]);
s[i].push_back(ket);
}
sort(s[i].begin(), s[i].end());
Tox tox(i);
q.push(tox);
}
for(int i=0;i<n/2*k;i++){
Tox cur=q.top();
q.pop();
cur.update();
q.push(cur);
}
//4-i lucumy
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
mni[i] = -1;
mxi[i] = -1;
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
Ket ket(i, j, x[i][j]);
sax.push_back(ket);
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
sort(sax.begin(), sax.end());
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (ismn[i][j]) {
res -= x[i][j];
}
if (ismx[i][j]) {
res += x[i][j];
}
}
}
for (int i = 0; i < n; i++) {
bool is_ap = true;
bool is_am = true;
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
is_ap = false;
}
if (ismn[i][j]) {
is_am = false;
}
}
if (is_am) {
am.push_back(i);
isam[i] = true;
}
else if (is_ap) {
ap.push_back(i);
isap[i] = true;
}
else {
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
mxc[i]++;
}
if (ismn[i][j]) {
mnc[i]++;
}
}
}
}
////cout << "-> " << ap.size() << " " << am.size() << endl;
//////cout << ap[0] << endl;
for (int r = 0; r < k; r++) {
for (int tox : am) {
give_max(tox, r);
}
int cnt = 0;
for (int tox : ap) {
give_min(tox, r);
cnt++;
}
int len = m - r - 1;
for (int tox = 0; tox < n; tox++) {
if (!isap[tox] && !isam[tox]) {
if (cnt < n / 2) {
give_min(tox, r);
if (mnc[tox] == 0) {
isam[tox] = true;
am.push_back(tox);
}
cnt++;
}
else {
give_max(tox, r);
if (mxc[tox] == 0) {
isap[tox] = true;
ap.push_back(tox);
}
}
}
}
}
allocate_tickets(ans);
return res;
}
/*
3 1 1 1 2 3
4 4 4 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1
7
4 4 4
5 8 6 9
4 1 5 2
3 6 5 7
8 4 5 9
29
5 5 5
1 2 3 6 5
4 8 5 2 7
9 4 5 8 9
5 6 4 8 4
2 5 1 4 6
69
5 5 4 1 2 3 6 5 4 8 5 2 7 9 4 5 8 9 5 6 4 8 4 2 5 1 4 6
4 4 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
4 4 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 5 4 4 4 5 4 4 4 5 4 4 4 5
4 4 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
5
4 4 2
1 5 6 2
2 9 4 8
6 4 2 5
3 4 7 8
23
0 1 -1 -1
-1 0 -1 1
1 0 -1 -1
1 -1 -1 0
*/
