Couvrir Le Segment
On vous donne une liste de
n segments, où chaque segment est représenté par et a un coût associé . On vous fournit également un segment [L, R] que vous devez couvrir.Vous devez couvrir le segment
[L, R] en sélectionnant un ensemble de segments dans la liste donnée afin que leur union inclue le segment [L, R]. Toutefois, sélectionner le i‑ème segment implique un coût de .Trouvez le coût minimum nécessaire pour couvrir le segment
[L, R].Entrée
La première ligne de l'entrée contient les entiers
n, L et R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), représentant respectivement le nombre de segments et le segment de requête.Les
n lignes suivantes contiennent trois entiers , et (), décrivant un segment et son coût associé.Sortie
Le programme doit afficher un seul entier : le coût minimum pour couvrir le segment
[L, R]. S'il est impossible de couvrir le segment [L, R], affichez -1 à la place.Exemples
Entrée | Sortie |
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