セグメントのカバー
n 個の線分のリストが与えられます。各線分は の形式で表され、それぞれコスト を持っています。さらに、カバー対象となる線分 [L, R] が指定されています。与えられたリストからいくつかの線分を選び、その合併が
[L, R] をすべて含むようにしなければなりません。ただし、i 番目の線分を選ぶと のコストがかかります。このとき、
[L, R] をカバーするのに必要な最小コストを求めてください。入力
最初の行には、
n, L, R が与えられます (1 ≤ n ≤ 100000, 1 ≤ L ≤ R ≤ )。これらは、それぞれ線分の個数とカバー対象となる線分を表します。続く
n 行では、3 つの整数 , , が与えられます ()。これは、それぞれ線分の両端点とその線分のコストを意味します。出力
[L, R] をカバーするために必要な最小コストを 1 つの整数で出力してください。もし [L, R] をカバーできない場合は、-1 を出力してください。例
入力 | 出力 |
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