#include <bits/stdc++.h>
#include "tickets.h"
#define ll long long
using namespace std;
struct Data{
int l,r,id;
bool operator < (const Data &o) const {
if(l!=o.l) return l < o.l;
return r < o.r;
}
};
const int MN = 1505;
int N,M,st[MN],en[MN];
ll ams;
ll sol_ans(vector<Data> x){
priority_queue<int> pq;
int sz = x.size();
ll best_ans = 0, cur = 0;
for(int i=0; i<sz; i++) {
if(i<sz/2) cur -= x[i].l, pq.push(x[i].r+x[i].l);
else cur += x[i].r;
}
best_ans = cur;
for(int i=sz/2; i<sz; i++){
cur += - x[i].l - x[i].r;
pq.push(- x[i].r - x[i].l);
cur += pq.top(); pq.pop();
best_ans = max(best_ans,cur);
}
return best_ans;
}
void debug(vector<int> v){cerr << "V: "; for(auto x:v) cerr << x << ' '; cerr << endl;}
vector<int> sol(vector<Data> x){
sort(x.begin(),x.end());
ll best_ans = sol_ans(x);
ams += best_ans;
priority_queue<pair<int,int>> pq;
int sz = x.size();
ll cur = 0;
vector<int> res(sz);
for(int i=0; i<sz; i++) {
if(i<sz/2) cur -= x[i].l, pq.push({x[i].r+x[i].l,x[i].id}), res[x[i].id] = 1;
else cur += x[i].r, res[x[i].id] = 0;
}
// debug(res);
if(best_ans==cur) return res;
for(int i=sz/2; i<sz; i++){
res[i] = 1;
cur += - x[i].l - x[i].r;
pq.push({- x[i].r - x[i].l,x[i].id});
auto tmp = pq.top(); pq.pop();
cur += tmp.first;
res[tmp.second] = 0;
// cerr << "ID: " << tmp.first << ' ' << tmp.second << endl;
// debug(res);
if(cur==best_ans) return res;
}
cerr << "SOL NOT RETURNING ANYTING\n";
exit(1);
}
long long find_maximum(int k, vector<vector<int>> x) {
N = x.size();
M = x[0].size();
vector<vector<int>> answer(N);
for(int i=0; i<N; i++) en[i] = M-1, answer[i].resize(M);
for(int i=0; i<N; i++) for(int j=0; j<M; j++) answer[i][j] = -1;
for (int t = 0; t < k; t++) {
vector<Data> row;
for (int i = 0; i < N; i++) {
row.push_back({x[i][st[i]],x[i][en[i]],i});
}
vector<int> v = sol(row);
for(int i=0; i<N; i++){
if(v[i]) {
answer[i][st[i]] = t;
st[i]++;
}
else{
answer[i][en[i]] = t;
en[i]--;
}
}
}
allocate_tickets(answer);
return ams;
}
