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