구간 덮기

1차원 평면에 $N$개의 선분이 존재한다. 1차원 평면상의 $x = S$부터 $x = E$까지의 구간을 주어진 선분을 최대 3개 사용하여 모두 덮으려 한다.

시작점이 $x=l$이고 끝점이 $x=r$인 선분이 점 $x$를 덮는다는 것은 $l \leq x \leq r$을 의미하고, 선분 집합 $L$이 $x=S$부터 $x=E$까지를 덮을 수 있다는 것은 $S \leq x \leq E$인 모든 실수 $x$에 대해 $x$를 덮는 선분이 $L$에 적어도 하나 이상 존재함을 의미한다.

이때, 구간을 덮는 방법에 따라 '오차'라는 값을 정의하자.

'오차'는 사용한 선분 중 서로 다른 2개를 골랐을 때 겹치는 구간의 길이의 합이다. 만약 선분 하나로 $x = S$부터 $x = E$까지 모두 덮을 수 있다면 이 방법의 오차는 0이다.

'오차'를 최소화하면서 $x = S$부터 $x = E$까지 최대 3개의 선분을 사용하여 덮어보고, '오차'의 최솟값을 출력하자.

첫 번째 줄에 선분의 개수 $N$, 시작점 $S$와 끝점 $E$가 공백으로 구분되어 주어진다.

이후 $N$줄에 걸쳐 그중 $i (1 \leq i \leq N)$번째 줄에 $i$번째 선분의 시작점 $s_i$와 끝점 $e_i$가 공백으로 구분되어 주어진다.

첫째 줄에 가능한 오차의 최솟값을 출력한다.

만약 어떻게 하더라도 $x=S$부터 $x=E$까지 덮을 수 없다면 $-1$을 출력한다.

• $1 \leq N \leq 1,000,000$
• $1 \leq s_i < e_i \leq 10^9$
• $1 \leq S < E \leq 10^9$
• 문제에서 주어지는 모든 수는 정수이다.