Copertura del Segmento
Vi viene fornito un elenco di
n segmenti, dove ciascun segmento è rappresentato come e ha un costo associato . Avete inoltre a disposizione un segmento che dovete coprire.Per coprire il segmento , è necessario selezionare un insieme di segmenti dall’elenco dato in modo che la loro unione includa il segmento . Tuttavia, selezionando il segmento
i-esimo si sostiene un costo pari a .Trovate il costo minimo necessario per coprire il segmento .
Input
La prima riga dell’input contiene gli interi
n, L e R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), che rappresentano il numero di segmenti e il segmento di interesse.Le successive
n righe contengono tre interi , e (), che descrivono ciascun segmento e il suo costo associato.Output
Il programma deve stampare un singolo intero: il costo minimo per coprire il segmento . Se è impossibile coprire , stampate
-1.Esempi
Input | Uscita |
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