구간 덮기

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

시작점이 $x=l$이고 끝점이 $x=r$인 선분은 $l \leq x \leq r$을 만족하는 점 $x$를 덮는다. 선분 집합 $L$이 구간을 덮는다는 것은 $S \leq x \leq E$인 모든 실수 $x$에 대해, $L$에 $x$를 덮는 선분이 적어도 하나 있다는 뜻이다.

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

최대 3개의 선분으로 구간을 덮되, '오차'가 가장 작은 값을 구한다.

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

이후 $N$개의 줄에 걸쳐 $i$번째 줄에 $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$
• 입력되는 모든 수는 정수이다.