import java.util.*;
class joi2019_ho_t4 {
static int n;
static long totalMoves = 0;
// Direcciones para el BFS: derecha, izquierda, arriba, abajo
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static class Position {
int x, y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Position)) {
return false;
}
Position p = (Position) o;
return x == p.x && y == p.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
static class BFSState {
Position pos;
long moves;
BFSState(Position pos, long moves) {
this.pos = pos;
this.moves = moves;
}
}
// BFS optimizado para encontrar el camino más corto
static long findShortestPath(Position start, Position target) {
// Si la distancia Manhattan es menor que un umbral, usamos cálculo directo
long manhattanDist = Math.abs((long)start.x - target.x) + Math.abs((long)start.y - target.y);
if (manhattanDist <= 1000) { // Umbral para optimización
return manhattanDist;
}
// Para distancias grandes, usamos BFS con límites optimizados
Queue<BFSState> queue = new LinkedList<>();
boolean[][] visited = new boolean[2001][2001]; // Ajustar según el rango de coordenadas
queue.offer(new BFSState(start, 0));
visited[start.x + 1000][start.y + 1000] = true; // Ajustar índices para evitar negativos
// Establecemos límites para la búsqueda basados en la posición objetivo
int minX = Math.min(start.x, target.x) - 1;
int maxX = Math.max(start.x, target.x) + 1;
int minY = Math.min(start.y, target.y) - 1;
int maxY = Math.max(start.y, target.y) + 1;
while (!queue.isEmpty()) {
BFSState current = queue.poll();
Position pos = current.pos;
if (pos.equals(target)) {
return current.moves;
}
// Exploramos las cuatro direcciones
for (int i = 0; i < 4; i++) {
int newX = pos.x + dx[i];
int newY = pos.y + dy[i];
// Verificamos límites optimizados
if (newX < minX || newX > maxX || newY < minY || newY > maxY) {
continue;
}
// Ajustar índices para evitar negativos
int adjustedX = newX + 1000;
int adjustedY = newY + 1000;
if (!visited[adjustedX][adjustedY]) {
queue.offer(new BFSState(new Position(newX, newY), current.moves + 1));
visited[adjustedX][adjustedY] = true;
}
}
}
return manhattanDist; // Fallback a distancia Manhattan si BFS falla
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int totalCoins = 2 * n;
List<Position> coins = new ArrayList<>();
List<Position> targets = new ArrayList<>();
// Lectura y procesamiento de posiciones iniciales
for (int i = 0; i < totalCoins; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
// Cálculo de movimientos iniciales a los límites
if (y < 1) {
totalMoves += Math.abs(1 - y);
y = 1;
}
if (y > 2) {
totalMoves += Math.abs(y - 2);
y = 2;
}
if (x < 1) {
totalMoves += Math.abs(1 - x);
x = 1;
}
if (x > n) {
totalMoves += Math.abs(x - n);
x = n;
}
coins.add(new Position(x, y));
}
// Creación de posiciones objetivo
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= 2; y++) {
targets.add(new Position(x, y));
}
}
// Emparejamiento de monedas con objetivos usando BFS
boolean[] usedCoins = new boolean[coins.size()];
boolean[] usedTargets = new boolean[targets.size()];
// Primera pasada: emparejar monedas en posiciones exactas
for (int i = 0; i < coins.size(); i++) {
if (usedCoins[i]) {
continue;
}
Position coin = coins.get(i);
for (int j = 0; j < targets.size(); j++) {
if (usedTargets[j]) {
continue;
}
Position target = targets.get(j);
if (coin.equals(target)) {
usedCoins[i] = true;
usedTargets[j] = true;
break;
}
}
}
// Segunda pasada: emparejar monedas restantes usando BFS
for (int i = 0; i < coins.size(); i++) {
if (usedCoins[i]) {
continue;
}
Position coin = coins.get(i);
long minDist = Long.MAX_VALUE;
int bestTarget = -1;
for (int j = 0; j < targets.size(); j++) {
if (usedTargets[j]) {
continue;
}
Position target = targets.get(j);
long dist = findShortestPath(coin, target);
if (dist < minDist) {
minDist = dist;
bestTarget = j;
}
}
if (bestTarget != -1) {
totalMoves += minDist;
usedCoins[i] = true;
usedTargets[bestTarget] = true;
}
}
System.out.println(totalMoves);
}
}
