Cubriendo el Segmento
Se te proporciona una lista de
n segmentos, donde cada segmento se representa como y tiene un costo asociado . También se te da un segmento [L, R] que necesitas cubrir.Para cubrir el segmento
[L, R], debes seleccionar un conjunto de segmentos de la lista de manera que la unión de los que elijas incluya al segmento [L, R]. Sin embargo, usar el segmento i tiene un costo de .Determina el costo mínimo necesario para cubrir el segmento
[L, R].Entrada
La primera línea de la entrada contiene los enteros
n, L y R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), que representan el número de segmentos y el segmento a cubrir, respectivamente.Las siguientes
n líneas contienen tres enteros , y (), que describen cada segmento y su costo asociado.Salida
Debes imprimir un solo entero: el costo mínimo para cubrir el segmento
[L, R]. Si no es posible cubrirlo, imprime -1.Ejemplos
Entrada | Salida |
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