우주 엘리베이터

오랜 재료 과학 연구 끝에, 과학자들은 오랫동안 구상되어 온 우주 엘리베이터를 떠받칠 만큼 강한 소재를 마침내 만들어 냈다!

엘리베이터는 정지궤도에서 지구에 고정되어 있어서, 지구 중력 우물을 넘는 효율적인 수직 운송을 가능하게 한다.

건설에는 막대한 공학 기술, 시간, 그리고 자금이 들어갔고, 첫 화물을 실어 나를 준비도 끝났다. 그런데 과학자들이 한 가지 큰 변수를 놓쳤다. 바로 들어올 요청의 개수다!

운영을 시작한 지 몇 분 만에 요청이 쏟아졌다. 국립우주기관은 국제우주정거장(ISS)에 물을 보내 달라고 요청했고, 행성 이해를 위한 대학 연합(ICPC)은 ISS에서 조립한 저중력 탐사선을 실어 달라고 했으며, 천문학과는 태양 플레어를 관측할 새로운 고고도 위성을 발사해 달라고 했다. 지역 기상대는 돌아오는 길에 잃어버린 고고도 기상 풍선을 회수할 수 있는지 물었다.

과정을 단순하게 하기 위해, 들어오는 요청은 주 단위로 모아서 처리하기로 했다. 시간과 에너지 손실은 거의 전적으로 이동한 거리에 따라 달라지며, 위치 에너지 같은 요소는 무시할 만하다.

과학자들은 지역 대학 컴퓨터공학과에 한 주의 요청을 입력받아, 모든 요청을 처리하기 위해 엘리베이터가 이동해야 하는 최소 수직 거리를 구하는 프로그램을 의뢰했다.

엘리베이터는 한 번에 실을 수 있는 짐의 개수에 제한이 없다. 특히 매우 큰 물체를 옮기는 요청은 따로 처리되기 때문이다. 또 엘리베이터는 모든 요청을 마치는 즉시 그 자리에서 멈출 수 있다. 그래서 입력에는 지난주에 멈춘 위치인 엘리베이터의 시작 위치도 포함된다.

첫 줄에 요청의 개수 $N$과 엘리베이터가 현재 멈춰 있는 높이 $H_0$이 차례로 주어진다 ($1 \leq N \leq 10^5$).

이어서 $N$개의 줄에 정수 $u_i$와 $v_i$가 주어진다. 이는 높이 $u_i$에서 물건을 싣고 높이 $v_i$에서 내려놓으라는 요청이다. 도킹 절차에는 높은 정밀도가 필요하므로, 모든 높이는 해수면 기준 밀리미터 단위로 주어진다.

모든 높이는 $0 \le H_0, u_i, v_i \le 5 \cdot 10^{11}$을 만족하며, $u_i \neq v_i$이다.

모든 요청을 처리하기 위해 엘리베이터가 이동해야 하는 최소 거리를 밀리미터 단위로 출력한다.