Exhausting Errands

시간 제한1초메모리 제한512 MB

요약

각 심부름은 한 집에서 물건을 싣고 다른 집에 내려놓는 일이다. 짐을 무한히 실을 수 있고 출발점과 도착점이 자유로울 때, 모든 심부름을 마치는 최단 이동 거리를 구한다. 출력은 그 거리 하나다. start와 end가 자유로우므로 각 심부름 구간을 오가며 겹치는 구간은 한 번만 지나면 된다. 모든 구간의 합집합을 덮는 최소 이동 거리를 계산하는 문제다. 각 구간 [min(a,b), max(a,b)]를 칠하고, 전체 구간의 합집합 길이를 구한 뒤, 시작점과 끝점을 합집합의 양 끝으로 잡으면 된다. 조각난 구간들의 총 길이와 조각 사이 간격을 더한 값이 답이다. 구간을 정렬해 병합하면 O(n log n)에 해결된다. 좌표 범위가 1e9까지이므로 좌표 압축 없이도 정렬만으로 충분하다. 핵심 관찰은 겹치는 구간을 여러 번 지날 필요가 없다는 점이다. 따라서 각 연결 요소의 양 끝을 연결하는 비용만 세면 된다. 결과적으로 모든 구간을 병합한 뒤, 각 병합 구간의 길이 합과 구간 사이의 빈 공간을 더한다. 시작 지점은 첫 구간의 왼쪽 끝, 끝 지점은 마지막 구간의 오른쪽 끝으로 잡는다. 이렇게 하면 모든 심부름을 완료하는 최소 거리를 얻는다.

난이도: 보통10점 중 6점
유형: 그리디, 구간, 구현
정답자: 아직 제출이 없습니다

문제

Dolly the delivery drone is out for a busy working day. It has to complete $n$ errands in a street where $\ell$ houses are lined up in a row, numbered in ascending order as $1, \dots, \ell$ . The distance between adjacent houses is $1$ . Each errand consists of picking up a package at some house $a$ and delivering it to another house $b$ . Dolly can start with any errand, complete the errands in any order, and is able to carry an unlimited number of packages at the same time. Your job is to find the minimal total distance Dolly has to cover to complete all errands. The delivery route can start and finish at arbitrary locations along the street.

Figure E.1: Illustration of Sample Input 1. The shortest route is $2 \rightarrow 1 \rightarrow 9 \rightarrow 4$ with length $14$ .

입력

The input consists of:

One line with two integers $\ell$ and $n$ ( $1 \le \ell \le 10^9$ , $1 \le n \le 10^5$ ), where $\ell$ is the number of houses in the street, and $n$ is the number of errands.
$n$ lines, each with two integers $a$ and $b$ ( $1 \le a, b \le \ell$ with $a \not= b$ ) describing an errand where a package must be picked up at house $a$ and be delivered to house $b$ .

출력

Output a single line with the minimal distance Dolly has to cover from picking up the first package until delivering the last package.

예제2

예제 1
입력
```
10 6
1 4
3 5
6 7
2 1
9 4
8 5
```
예상 출력
```
14
```
예제 2
입력
```
100 3
11 50
50 49
36 35
```
예상 출력
```
42
```