택시

Bessie는 농장의 다른 소들을 위해 택시 서비스를 운영하고 있습니다. 소들은 길이가 $M$ ($1 \le M \le 10^9$)인 울타리를 따라 여러 위치에 모여 있습니다. 소들은 지금 있는 곳이 지루해져서 저마다 울타리를 따라 다른 곳으로 이동하고 싶어 합니다. Bessie는 각 소를 출발 위치에서 태워 목적지까지 데려다주어야 합니다.

Bessie의 차는 작아서 한 번에 소를 한 마리만 태울 수 있습니다. 소는 순간적으로 차에 타고 내릴 수 있습니다.

기름을 아끼기 위해 Bessie는 운전 거리를 최소로 하고 싶어 합니다. $N$마리 ($1 \le N \le 10^5$)의 소 각각에 대해 출발 위치와 도착 위치가 주어질 때, Bessie가 운전해야 하는 최소 총 거리를 구하세요. 기름을 가장 많이 아끼려면 때로는 소를 목적지가 아닌 위치에 잠시 내려놓아야 할 수도 있습니다.

Bessie는 울타리의 가장 왼쪽 지점인 위치 $0$에서 출발하며, 여정을 반드시 가장 오른쪽 지점인 위치 $M$에서 마쳐야 합니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 공백으로 구분된 두 정수 $s_i$와 $t_i$ ($0 \le s_i, t_i \le M$)가 주어지며, 각각 $i$번째 소의 출발 위치와 도착 위치를 나타냅니다.

• 첫째 줄: Bessie가 운전해야 하는 최소 총 거리를 나타내는 정수 하나. 결과는 32비트 정수 범위를 넘을 수 있음에 유의하세요.

소를 항상 목적지까지 곧장 데려다줄 필요는 없다는 점에 주목하면 도움이 됩니다. 소를 중간 지점에 잠시 내려놓았다가 나중에 다시 태우면, 빈 차로 이동하는 거리를 줄일 수 있는 경우가 있습니다.

전체 운전 거리는 두 부분으로 나눌 수 있습니다. 첫째, 각 소를 출발 위치에서 도착 위치까지 옮기는 거리로, 이는 항상 $\sum_i |s_i - t_i|$ 입니다. 둘째, 한 소를 내려준 뒤 다음 소를 태우러 가는 빈 차 이동 거리입니다. 빈 차 이동이 시작될 수 있는 위치의 집합은 $\{0\} \cup \{t_i\}$, 끝날 수 있는 위치의 집합은 $\{s_i\} \cup \{M\}$ 이며, 두 집합을 각각 정렬해 순서대로 짝지어 거리의 합을 구하면 빈 차 이동 거리를 최소화할 수 있습니다.