Cobrir o Segmento
É-lhe fornecida uma lista de
n segmentos, em que cada segmento é representado como e possui um custo associado . Recebe também um segmento [L, R] que é necessário cobrir.Para cobrir o segmento
[L, R], deve selecionar um conjunto de segmentos de tal forma que a união destes inclua [L, R]. No entanto, selecionar o i-ésimo segmento implica pagar um custo de .Determine o custo mínimo para cobrir o segmento
[L, R].Entrada
A primeira linha da entrada contém os inteiros
n, L e R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), que representam o número de segmentos e o segmento a cobrir, respetivamente.As seguintes
n linhas contêm três inteiros , e (), descrevendo cada segmento e o seu custo.Saída
O programa deve imprimir um único inteiro: o custo mínimo para cobrir o segmento
[L, R]. Se for impossível cobrir o segmento [L, R], imprima -1.Exemplos
Entrada | Saída |
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