시위

이번 일요일에 바이트타운에서 바이트의 날 행사가 열린다. 바이트랜드에서 가장 중요한 연례 행사 중 하나다. 그런데 올해는 조용한 마을 잔치로 끝나지 않을 분위기다.

바이트타운 시민은 한 가지 문제로 심하게 갈라져 있다. 전통에 따라 1바이트는 언제나 8비트여야 한다고 믿는 쪽이 있고, 용량이 더 넉넉한 16비트 바이트로 가자는 진보파도 있다. 훨씬 완고하게 1바이트는 4비트뿐이어야 한다고 선언하려는 쪽도 있다. 규모가 작은 반체제 모임도 있는데, 바이트의 비트 수가 2의 거듭제곱이면 안 된다거나 짝수일 필요조차 없다고 주장한다. 이 단체는 모두 자기 주장을 시민에게 설득하려고 각각 시위를 열 계획이다.

시위가 이렇게 많으면 바이트의 날 행사에 방해가 될까 걱정하는 시민이 많다. 시장은 시위 일부를 금지하면 지지를 크게 얻을 수 있다고 판단했다. 이런 결정은 논란을 부르니 시위는 최대 두 개만 취소하기로 했다. 그리고 취소한 뒤에 도시에서 시위가 진행되는 시간의 총합이 최대한 짧아지도록 취소할 시위를 고르려 한다. 시위 여러 개가 겹치는 시간은 한 번만 센다. 시위가 진행되는 시간의 총합을 얼마나 줄일 수 있는지 구해서 시장을 도와주자.

첫 줄에 계획된 시위의 수 $n$ ($2 \le n \le 500\,000$)이 주어진다. 이어지는 $n$개의 줄은 각각 시위 하나를 설명한다. 그중 $i$번째 줄에는 정수 $a_i$와 $b_i$ ($0 \le a_i < b_i \le 10^9$)가 주어지고, $i$번째 시위가 일출 후 $a_i$ 바이트분에 시작해서 일출 후 $b_i$ 바이트분에 끝난다는 뜻이다.

시장이 시위를 최대 두 개 취소했을 때 줄일 수 있는 시간의 최댓값을 음이 아닌 정수 하나로 출력한다.

예제에서 시장은 첫 번째 시위와 네 번째 시위의 허가를 내주지 않으면 된다.