Covering The Segment

You are given a list of n segments, where each segment is represented as and has an associated cost . You are also given a segment [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 , and (), describing a segment and its associated cost.

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

To check your solution you need to sign in