15713번 - 오리날다

나는 꿈을 꾸었죠 네모난 달이 떴죠~! 하늘위로 올라가 달에게 말을 했죠 ~♬

늦은 밤 잠에서 깨어 날개를 흔들었죠 오리는 날 수 없다 엄마에게 혼났죠

이제는 하늘로 날아갈래요 하늘 위 떠있는 멋.진. 달 되고 싶어 !! ★

그렇다. 예상했던 대로 우리는 오리를 하늘로 올라갈 수 있게 도와줘야 한다. 오리는 y축만 있는 공간에 있으며, 그 곳에는 서로 다른 N개의 트램펄린이 있다. (y축만 있는 공간이지만, 같은 위치에 여러 개의 트램펄린이 존재할 수도 있다!) i번 트램펄린은 위치 y_i에 있고, 해당 트램펄린을 밟을 경우 오리는 정확히 h_i만큼 도약해서 y_i + h_i까지 올라가게 된다. 그리고 다시 중력의 영향으로 지면을 향해 떨어진다. 오리는 멈춰있거나 떨어지는 도중에 원하는 트램펄린을 다시 밟을 수 있다.

오리는 최소한의 거리만을 이동하고 싶어 하기 때문에 우리는 오리가 하늘에 도착할 때까지 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성해야 한다.

단, 오리는 현재 0의 위치에 있으며 오리는 하늘에 닿기만 해도 하늘에 도착한 것으로 간주한다. 편의상 오리의 크기는 0으로 생각하며, 이동할 때 다른 트램펄린과의 충돌은 무시한다.

첫째 줄에 트램펄린의 개수 N(1 ≤ N ≤ 10⁵)과 하늘의 높이를 의미하는 정수 S(1 ≤ S ≤ 10⁹)가 주어진다.

다음 N개의 줄에는 각각 한 줄씩 두개의 정수 i번째 트램펄린의 위치 y_i(0 ≤ y_i ≤ 10⁹)와 해당 트램펄린을 밟을 경우 도약하는 높이 h_i(0 ≤ h_i ≤ 10⁹)가 주어진다.

오리가 하늘에 도착할 때까지 이동해야 하는 거리의 최솟값을 출력하라.

만약 오리가 하늘에 도착할 수 없다면 "Ducks can't fly"를 출력하라.

1번째, 3번째, 4번째 트램펄린을 순서대로 밟으면 된다.

오리는 (0~7), (7~6), (6~9), (9~10) 구간을 이동하므로 정답은 12이다.

10에 닿는 순간 오리는 하늘에 도착한 것으로 간주함에 유의하라.