수상 택시
시간 제한1초메모리 제한128 MB
0에서 출발해 M에 도착해야 하는 배가 강을 따라 여러 승객을 태우고 각자의 목적지에 내려줄 때 필요한 최소 이동 거리를 구하는 문제입니다.
문제
상근이가 사는 도시에는 큰 강이 흐르고, 모든 집은 강을 따라 놓여 있다. 집은 0번부터 M번까지 번호가 매겨져 있으며, 이웃한 두 집 사이의 거리는 모두 1킬로미터이다.
상근이는 0번 집에 살고, 보트로 사람들을 태워 주는 일을 한다. 오늘 상근이는 저녁까지 M번 집에 도착해야 하며, 가는 길에 보트를 타려는 사람들을 모두 목적지까지 데려다주려고 한다.
오늘 보트를 타려는 사람은 N명이다. 각 사람마다 타는 위치와 내리는 위치가 주어지고, 보트는 충분히 커서 N명을 모두 동시에 태울 수 있다.
상근이는 모든 사람을 목적지까지 데려다준 뒤 M번 집에 도착해야 한다. 이때 이동해야 하는 거리의 최솟값을 구하시오.
입력
첫째 줄에 N과 M이 주어진다. N <= 300,000, 3 <= M <= 10^9 이다.
다음 N개 줄에는 각 사람이 보트에 타는 위치와 목적지가 주어진다. 모든 위치는 0 이상 M 이하의 정수이다.
출력
상근이가 모든 사람을 데려다주고 M번 집에 도착하기 위해 이동해야 하는 거리의 최솟값을 출력한다.