#include <bits/stdc++.h>
using namespace std;
#ifndef ARTHUR_LOCAL
#include "tickets.h"
#endif
using ll = long long;
#define len(x) int((x).size())
#define ff first
#define ss second
#ifdef ARTHUR_LOCAL
void allocate_tickets(vector<vector<int>> ans)
{
for(auto a:ans)
{
for(auto b:a) cout << b << " ";
cout << endl;
}
}
#endif
ll find_maximum(int k, vector<vector<int>> X)
{
int n = len(X);
int m = len(X[0]);
vector<vector<int>> answer;
for (int i = 0; i < n; i++)
{
vector<int> row(m);
for(int j = 0; j < m; j++)
{
row[j] = -1;
}
answer.push_back(row);
}
vector<pair<pair<ll,ll>,int>> V;
for(int i=0; i<n; i++)
{
V.push_back({{X[i][0],X[i][m-1]},i});
}
sort(V.begin(),V.end());
pair<ll,int> ans = {-1LL,-1};
for(int i=int(n/2)-1; i<n; i++)
{
vector<pair<ll,int>> options;
ll cur_ans = 0LL;
int locked_in = 1;
for(int j=0; j<i; j++)
{
if(V[j].ff.ss < V[i].ff.ff)
{
locked_in++;
cur_ans += V[i].ff.ff - V[j].ff.ff;
}
else
{
options.push_back({(V[i].ff.ff - V[j].ff.ff) - (V[j].ff.ss - V[i].ff.ff), j});
}
}
if(locked_in > int(n/2)) continue;
sort(options.rbegin(),options.rend());
for(auto opt:options)
{
int j = opt.ss;
if(locked_in < int(n/2))
{
locked_in++;
cur_ans += V[i].ff.ff - V[j].ff.ff;
}
else
{
cur_ans += V[j].ff.ss - V[i].ff.ff;
}
}
for(int j = i+1; j<n; j++)
{
cur_ans += V[j].ff.ss - V[i].ff.ff;
}
// cout << i << " " << cur_ans << " is curans\n";
ans = max(ans, {cur_ans,i});
}
if(true)
{
int i = ans.ss;
answer[V[i].ss][0]=0;
vector<pair<ll,int>> options;
ll cur_ans = 0LL;
int locked_in = 1;
for(int j=0; j<i; j++)
{
if(V[j].ff.ss < V[i].ff.ff)
{
locked_in++;
cur_ans += V[i].ff.ff - V[j].ff.ff;
answer[V[j].ss][0]=1;
}
else
{
options.push_back({(V[i].ff.ff - V[j].ff.ff) - (V[j].ff.ss - V[i].ff.ff), j});
}
}
// if(locked_in > int(n/2)) continue;
sort(options.rbegin(),options.rend());
for(auto opt:options)
{
int j = opt.ss;
if(locked_in < int(n/2))
{
locked_in++;
cur_ans += V[i].ff.ff - V[j].ff.ff;
answer[V[j].ss][0]=0;
}
else
{
cur_ans += V[j].ff.ss - V[i].ff.ff;
answer[V[j].ss][m-1]=0;
}
}
for(int j = i+1; j<n; j++)
{
cur_ans += V[j].ff.ss - V[i].ff.ff;
answer[V[j].ss][m-1]=0;
}
}
// cout << ans.ff << " " << ans.ss << endl;
allocate_tickets(answer);
return ans.ff;
}
#ifdef ARTHUR_LOCAL
int main()
{
find_maximum(1, {{1,3},{1,2}});
}
#endif
