Covering an Interval

Time limit2sMemory limit1024 MB

Summary

Given N segments on a line, pick at most three that cover the interval from S to E, minimizing the total length of overlaps between the chosen pairs.

Level: Medium6 of 10
Topics: Intervals, Sorting, Dynamic programming
Solved: No attempts yet

Problem

There are $N$ segments on a one-dimensional line. You want to cover the interval from $x = S$ to $x = E$ using at most 3 of the given segments.

A segment with start point $x=l$ and end point $x=r$ covers a point $x$ when $l \leq x \leq r$ . A set of segments $L$ can cover the interval when, for every real number $x$ with $S \leq x \leq E$ , at least one segment in $L$ covers $x$ .

The 'error' of a covering is the sum of the lengths of the overlaps between every pair of two different segments used. If one segment alone covers the whole interval from $x = S$ to $x = E$ , the error of that covering is 0.

Find the minimum possible 'error' over all coverings that use at most 3 segments.

Input

The first line contains the number of segments $N$ , the start point $S$ , and the end point $E$ , separated by spaces.

The next $N$ lines contain the start point $s_i$ and the end point $e_i$ of the $i$ -th segment, separated by spaces.

Output

Print the minimum possible error on the first line.

If the interval from $x=S$ to $x=E$ cannot be covered in any way, print $-1$ .

Limits

$1 \leq N \leq 1,000,000$
$1 \leq s_i < e_i \leq 10^9$
$1 \leq S < E \leq 10^9$
All numbers in the input are integers.

Examples2

Example 1
Input
```
3 1 10
1 7
2 10
3 6
```
Expected output
```
5
```

Example 2

Input

Expected output

-1