시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 98 22 17 34.694%

문제

상근이는 점점 부자가 되었고 트럭 운송 회사를 차렸다. 이 회사에는 트럭이 총 N대 있고, 모든 배달은 "공부 고속도로"를 통해 이루어진다.

공부 고속도로에는 나들목(인터체인지, IC)이 1,000,000개 있다. 그리고, 각 나들목은 1번부터 순서대로 번호가 매겨져 있다. 나들목에서는 고속도로로 들어오거나 나갈 수 있다.

고속도로에 들어갈 때는 들어온 나들목의 번호가 적혀있는 티켓을 하나 받게 된다. 이 티켓은 고속도로에서 나갈 때 요금소(톨게이트)에 제시해야하고, 들어온 나들목과 나가는 나들목 번호의 차이만큼 요금을 내야 한다. 예를 들어, 티켓에 적혀있는 나들목의 번호가 30이고 12번 나들목으로 나간다면, 요금은 18원이 된다.

고속도로 이용 요금은 점점 회사가 감당할 수 없는 수준까지 치솟았고, 상근이는 획기적인 방법을 생각해냈다. 바로, 고속도로 중간에서 두 운전사가 만나서 티켓을 교환하는 것이다. 이 방법은 서로 경로가 겹치지 않더라도 교환할 수 있으며, 티켓은 여러 번 교환할 수 있다.

하지만, 의심을 피하기 위해서 티켓에 적혀있는 나들목의 번호와 같은 나들목으로 나갈 수는 없다. 

운전사끼리 티켓을 적절히 교환했을 때, 내야하는 고속도로 이용 요금의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 트럭의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 트럭이 들어온 나들목의 번호와 나가야 하는 나들목의 번호가 공백으로 구분되서 주어진다. 나들목의 번호는 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다.

두 트럭이 고속도로로 들어올 때 사용하는 나들목의 번호나 나갈 때 사용하는 나들목의 번호가 같은 경우는 없다.

출력

상근이네 트럭 운송 회사가 내야하는 고속도로 이용 요금의 최소값을 출력한다. 이 값은 32비트 정수 범위를 넘어갈 수 있기 때문에, 64비트 정수(C/C++: long long)을 사용해야 한다.

예제 입력

3
3 65
45 10
60 25

예제 출력

32

힌트