Covering The Segment
You are given a list of
n segments, where each segment is represented as [L, R] that you need to cover.You should cover the segment
[L, R] by selecting a set of segments from the given list such that their union includes the segment [L, R]. However, selecting the i-th segment incurs a cost of Find the minimum cost to cover the segment
[L, R].Input
The first line of the input contains the integers
n, L, and R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), representing the number of segments and the query segment respectively.The next
n lines contain three integers Output
The program should print a single integer - the minimum cost to cover the segment
[L, R]. If it’s impossible to cover the segment [L, R], print -1 instead.Examples
Input | Output |
5 3 10
1 3 2
1 5 5
3 7 4
6 10 3
5 10 5 | 9 |
3 1 5
1 2 4
1 3 7
2 4 3 | -1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB