// ChatGPT 4o mini
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
struct Cell {
int row, col, coins;
Cell(int r, int c, int coin_count) : row(r), col(c), coins(coin_count) {}
};
// Function to calculate minimum cost to make all cells contain exactly 1 coin
int min_cost_to_redistribute(int n, vector<vector<int>>& a) {
vector<Cell> cells;
// Step 1: Populate the cells list with the position and coin counts
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
cells.push_back(Cell(i, j, a[i][j]));
}
}
// Step 2: Sort the cells by row and then by column (row-major order)
sort(cells.begin(), cells.end(), [](const Cell& c1, const Cell& c2) {
return c1.row < c2.row || (c1.row == c2.row && c1.col < c2.col);
});
int total_cost = 0;
// Step 3: Separate cells into excess and deficit
vector<Cell> excess, deficit;
for (auto& cell : cells) {
if (cell.coins > 1) {
excess.push_back(Cell(cell.row, cell.col, cell.coins - 1)); // excess coins
} else if (cell.coins < 1) {
deficit.push_back(Cell(cell.row, cell.col, 1 - cell.coins)); // deficit coins
}
}
int ex_idx = 0, de_idx = 0;
// Step 4: Move coins from excess to deficit
while (ex_idx < excess.size() && de_idx < deficit.size()) {
// Determine how many coins to move
int move = min(excess[ex_idx].coins, deficit[de_idx].coins);
// Calculate cost of moving these coins
int cost = move * (abs(excess[ex_idx].row - deficit[de_idx].row) + abs(excess[ex_idx].col - deficit[de_idx].col));
total_cost += cost;
// Update the remaining coins in excess and deficit
excess[ex_idx].coins -= move;
deficit[de_idx].coins -= move;
// Move to the next excess or deficit if no more coins need to be moved
if (excess[ex_idx].coins == 0) {
++ex_idx;
}
if (deficit[de_idx].coins == 0) {
++de_idx;
}
}
return total_cost;
}
signed main() {
// Example input
int n;
cin>>n;
vector<vector<int>>a(2*n);
for(int i=0;i<2*n;i++){
a[i].resize(2);
cin>>a[i][0]>>a[i][1];
}
int ans=0;
for(int i=0;i<2*n;i++){
if(a[i][0]<1){
ans+=1-a[i][0];
a[i][0]=1;
}
if(a[i][0]>n){
ans+=a[i][0]-n;
a[i][0]=n;
}
if(a[i][1]<1){
ans+=1-a[i][1];
a[i][1]=1;
}
if(a[i][1]>2){
ans+=a[i][1]-2;
a[i][1]=2;
}
}
vector<vector<int>>c(n);
for(int i=0;i<n;i++){
c[i].resize(2);
}
for(int i=0;i<2*n;i++){
c[a[i][0]-1][a[i][1]-1]++;
}
// Compute the minimum cost
int result = min_cost_to_redistribute(n, c);
cout << ans + result << endl;
return 0;
}
