밀레니엄 웜

밀레니엄 웜은 수천만 년 전에 지구 표면에서 사라진 고대 생물이다. 그래서 이 생물에 대해 알려진 것은 거의 없다. 최근 귀중한 밀레니엄 웜 화석이 여러 개 발견되면서 고고학자들이 이 종에 관심을 갖기 시작했다. 이 화석들은 생물의 전체 모습을 거의 그대로 보존하고 있다.

이론 과학자들은 이 화석으로 형태 모델을 세웠고, 밀레니엄 웜이 지네의 조상이라고 결론지었다. 그러나 과학자 J는 실제와 이론 사이에 차이가 있다는 것을 발견했다. 수백 개의 화석을 연구한 결과, 대부분의 밀레니엄 웜 구조가 이론 모델과 완전히 들어맞지 않았다. 이론 과학자 K는 화석 상태에서 여러 종류의 변화가 일어날 수 있다고 지적한다. 아주 작은 변화라도 모델과 어긋나는 결과를 낳을 수 있다.

이제 과학자들에게 새로운 문제가 생겼다. 주어진 밀레니엄 웜 화석이 이론 모델과 얼마나 다른지 예측하는 것이다. 구체적으로, 화석 모양 A가 주어졌을 때, 이론 모델에 맞으면서 화석화 과정에서 A가 되었을 가능성이 가장 큰 모양 B를 찾아야 한다.

이론 과학자들이 제안한 밀레니엄 웜의 신체 특징 모델은 왼쪽 그림과 같다. 몸은 머리, 꼬리, 몸통, 발이라는 네 가지 주요 부분으로 이루어진다.

1. 머리와 꼬리는 서로 평행한 한 쌍의 선분으로 나타난다. 머리와 꼬리에 평행한 방향을 x 방향, 이에 수직인 방향을 y 방향이라고 한다.
2. 머리와 꼬리 사이는 서로 교차하지 않는 두 개의 접힌 선분으로 이어진다. 이 선분들은 머리, 꼬리와 함께 몸통이라는 영역을 둘러싼다. 접힌 각은 모두 둔각이거나 평각이다. 선분의 개수는 홀수여야 하며, 위에서 아래로 셌을 때 x 방향에 수직인 선분의 개수도 홀수여야 한다.
3. 위에서 아래로 셌을 때 접힌 선분 중 짝수 번째 선분에 해당하는 몸통에는 한쪽 면에서 발이 하나씩 돋아 있다. 발의 윗변과 아랫변은 x 방향과 평행하며, 사다리꼴이거나 직사각형이다. 몸통 반대편을 향한 변은 x 방향에 수직이다.

발의 모양이 삼각형이 될 수는 없으므로, 각 발의 밑변 길이는 0보다 크다. 몸통 양쪽의 발 개수는 서로 달라도 된다.

xy 좌표계에서 몸통과 발이 이루는 입체 영역의 경계는 모두 축에 평행하거나 수직이다. 간단히 하기 위해 이 경계선의 길이는 양의 정수라고 가정한다. 따라서 각 밀레니엄 웜의 몸은 단위 정사각형들의 집합으로 표현할 수 있고, 각 단위는 좌표 (x, y)로 정해진다. 머리와 꼬리 사이의 거리를 $n$이라 하면, 밀레니엄 웜 B는 $2n$개의 정수로 기술된다. B를 x 방향에 평행한 너비 1의 띠 $n$개로 나눈다. i번째 띠에서 가장 왼쪽 단위의 x 좌표를 $L_i$, 가장 오른쪽 단위의 x 좌표를 $R_i$라 하면, $(n, L_1, L_2, ..., L_n, R_1, R_2, ..., R_n)$이 밀레니엄 웜 하나를 정한다.

오랜 세월의 침식 때문에 실제 화석의 모양은 이론 모델의 명세를 만족하지 않는다. 몸의 일부 칸은 광물에 의해 부식되었다.

지질학자, 물리학자, 생물학자들은 다음을 결론지었다.

1. 부식은 칸 단위로 일어난다. 칸 전체만 부식될 수 있다.
2. 부식은 단계별로 일어나며, 한 단계마다 칸 하나만 부식된다.
3. 어떤 칸을 제거했을 때 몸이 여전히 연결되어 있다면, 그 칸은 부식될 수 없다.
4. 어떤 칸의 왼쪽 이웃과 오른쪽 이웃이 모두 부식되지 않았다면, 그 칸은 지금 부식될 수 없다.
5. 머리에 인접한 칸들이 모두 부식될 수는 없다. 꼬리에 인접한 칸들이 모두 부식될 수도 없다.

이 다섯 조건을 만족하면, 부식된 화석은 $L'_i \le R'_i$인 $(n, L'_1, L'_2, ..., L'_n, R'_1, R'_2, ..., R'_n)$로 나타낼 수 있다. 아래 그림은 예시이다.

화석 A의 명세 $\langle n, L', R' \rangle$이 주어지면, 이론 설명을 만족하는 명세 $\langle n, L, R \rangle$의 B를 구하라. B는 부식 과정을 거쳐 A로 바뀔 수 있어야 하며, B를 A로 바꾸는 데 드는 비용(부식되어야 하는 칸의 수)이 최소가 되어야 한다. 그 최소 단계 수를 출력하라.

첫째 줄에 정수 $n$이 주어진다.

이어지는 $n$개의 줄에는 각각 공백으로 구분된 두 정수 $L'_i$와 $R'_i$가 주어진다. $i$번째 줄에는 $L'_i$와 $R'_i$가 있다.

최소 비용을 나타내는 정수 하나를 한 줄에 출력한다.

$n \le 1000000$

$0 \le L'_i \le R'_i \le 1000000$

입력 데이터는 유효함이 보장된다.