Das Segment abdecken
Sie haben eine Liste mit
n Segmenten, wobei jedes Segment durch dargestellt wird und einen zugehörigen Kostenwert besitzt. Außerdem wird Ihnen ein Zielsegment [L, R] gegeben, das Sie abdecken müssen.Dazu wählen Sie eine Teilmenge aus den gegebenen Segmenten aus, deren Vereinigung das Segment
[L, R] vollständig überdeckt. Das Auswählen des i-ten Segments verursacht Kosten in Höhe von .Ziel ist es, für das Segment
[L, R] die kleinsten Gesamtkosten zu bestimmen, unter denen eine vollständige Überdeckung möglich ist.Eingabe
Die erste Zeile enthält die drei Ganzzahlen
n, L und R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ). Damit wird festgelegt, wie viele Segmente es gibt und welches das zu überdeckende Segment ist.Die folgenden
n Zeilen enthalten jeweils drei Ganzzahlen , und (). Jede Zeile beschreibt ein Segment zusammen mit den dazugehörigen Kosten.Ausgabe
Geben Sie eine einzelne Ganzzahl aus – die minimalen Kosten, um das Segment
[L, R] zu überdecken. Lässt sich das Segment [L, R] nicht überdecken, so geben Sie stattdessen -1 aus.Beispiele
Eingabe | Ausgabe |
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