레이팅 미적용하루 동안 Luka의 트럭 \(N\)대가 특정 고속도로를 달린다. 이 고속도로에는 여러 출구와 입구가 있다. 특정 번호의 출구는 같은 번호의 입구와 같은 위치에 있다.
고속도로에 들어갈 때 트럭 운전사는 자신이 이용한 입구가 표시된 통행권을 받는다. 나갈 때 운전사는 입구 번호와 출구 번호의 차의 절댓값만큼 통행료를 낸다. 예를 들어 통행권에 입구 \(30\)을 이용했다고 적혀 있으면, 출구 \(12\)로 나갈 때 \(18\)을 내야 한다.
Luka는 회사가 매일 쓰는 통행료를 아낄 방법을 알아냈다. 어떤 두 운전사든 경로가 겹치지 않더라도 고속도로에서 만나 통행권을 교환할 수 있다. 통행권은 몇 번이든 교환할 수 있다.
다만 통행권에 같은 번호의 입구를 이용했다고 적혀 있으면 그 번호의 출구로는 나갈 수 없다. 의심을 살 것이기 때문이다.
운전사들이 통행권을 교환하여 낼 수 있는 최소 총 통행료를 계산하는 프로그램을 작성하시오.
첫째 줄에 트럭의 수인 정수 \(N\) (\(1 \le N \le 100\,000\))이 주어진다.
다음 \(N\)개의 줄에는 \(1\) 이상 \(1\,000\,000\) 이하의 서로 다른 두 정수가 주어진다. 순서대로 트럭 한 대의 입구 번호와 출구 번호이다.
같은 고속도로 입구나 같은 출구를 이용하는 두 트럭은 없다.
Luka의 회사가 내야 하는 최소 총 통행료를 출력한다.
참고: 64비트 정수 자료형(C/C++의 long long, Pascal의 int64)을 사용하시오.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 80점 |
3
3 65
45 10
60 2532The first and third drivers exchange tickets, then the second and third do. The drivers end up with tickets 60, 3, 45, for a total of |65-60| + |10-3| + |25-45| = 32.
3
5 5
6 7
8 85