전기

19세기에 전기는 서서히 일상에 보급되고 있었다. 전기를 대규모로 처음 활용한 분야 가운데 하나는 공공장소의 조명이었다. Edison Patents & Theft 사는 맨해튼의 주요 거리에 불을 밝혀서 뉴욕시 당국에 전기가 얼마나 쓸모 있는지 보여 주기로 했다. 맨해튼은 매우 규칙적인 구조이며 스트리트($X$축에 평행)와 애비뉴($Y$축에 평행)로만 이루어져 있다.

기술이 아직 걸음마 단계라서 조명은 구역 단위로 설치한다. 구역 하나는 두 스트리트와 두 애비뉴 위에 변이 놓인 직사각형이다. 각 구역은 직사각형의 마주 보는 두 꼭짓점으로 주어지고, 꼭짓점은 항상 스트리트와 애비뉴의 교차로에 있다. 구역끼리 겹칠 수 있다. 구역마다 닫힌 회로 하나로 조명을 켜는데, 기술의 한계로 이 회로에는 구역의 꼭짓점마다 하나씩 모두 네 개의 차단점만 있다.

조명할 구역을 정한 회사는 발전소를 세우기에 가장 유리한 교차로를 찾으려 한다. 발전소 설치 비용은 발전소에서 각 구역까지의 거리를 모두 더한 값이다. 발전소에서 한 구역까지의 거리는 발전소와 그 구역에서 가장 가까운 꼭짓점 사이에 있는 스트리트 수와 애비뉴 수의 합, 즉 두 점 사이의 맨해튼 거리이다. 발전소가 $(p_x, p_y)$에 있을 때 꼭짓점 $(v_x, v_y)$까지의 거리는 $|p_x - v_x| + |p_y - v_y|$이고, 구역 $(x_1, y_1, x_2, y_2)$까지의 거리는 네 꼭짓점 $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_1)$, $(x_2, y_2)$에 대한 이 값 가운데 최솟값이다. 발전소는 정수 좌표로 된 아무 교차로에나 세울 수 있다. 그림은 구역을 고른 한 가지 예와 발전소 위치를 보여 준다.

21세기의 기술로 이 문제를 풀어서, 주어진 구역에 대해 발전소 설치 비용의 최솟값을 구하라.

첫째 줄에 구역의 수 $N$ $(1 \le N \le 200\,000)$이 주어진다.

다음 $N$개의 줄에 구역이 하나씩 주어진다. 각 구역은 네 좌표 $x_1$, $y_1$, $x_2$, $y_2$로 주어지며 $x_1 < x_2$, $y_1 < y_2$이다. 좌표는 모두 $10^7$(천만)보다 작은 자연수이다.

첫째 줄에 발전소 설치 비용의 최솟값을 출력한다.