택시 기사

택시 기사 민준은 좌표 평면 위에서 N명의 손님을 모두 태워 목적지까지 데려다 주어야 한다. 각 손님은 출발지와 목적지 좌표가 있으며, 반드시 출발지에서 태운 후 목적지에서 내려줘야 한다. 택시는 처음 원점(0, 0)에서 출발하며, 이동 거리는 맨해튼 거리를 사용한다.

모든 손님을 태우고 내려주는 최소 총 이동 거리를 구하여라.

입력

첫째 줄에 손님 수 N이 주어진다. 다음 N줄에 걸쳐 각 손님의 출발지 좌표(sx, sy)와 목적지 좌표(dx, dy)가 공백으로 구분되어 주어진다.

출력

최소 총 이동 거리를 출력한다.

제한

• 1 ≤ N ≤ 4
• 0 ≤ sx, sy, dx, dy ≤ 20

예제 입력 1

1
0 0 1 1

예제 출력 1

2

예제 입력 2

2
0 1 3 2
2 0 4 3

예제 출력 2

9

설명: 예제 1에서 택시가 이미 (0,0)에 있고 손님 출발지도 (0,0)이므로 이동 없이 바로 태우고, 목적지 (1,1)까지 맨해튼 거리 2를 이동한다.