Покрытие отрезка
Вам дан список из
n отрезков, каждый из которых задаётся в виде и имеет связанную с ним стоимость . Также у вас есть отрезок [L, R], который нужно покрыть.Необходимо покрыть отрезок
[L, R], выбрав некоторый набор из данных отрезков таким образом, чтобы их объединение полностью содержало [L, R]. При этом выбор i-го отрезка влечёт за собой затраты в размере .Найдите минимальную суммарную стоимость, необходимую для покрытия отрезка
[L, R].Ввод
В первой строке входных данных заданы целые числа
n, L и R (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), где n – это количество отрезков, а L и R – границы отрезка, который нужно покрыть.В следующих
n строках приведены три целых числа , и (), которые описывают границы отрезка и его стоимость.Вывод
Выведите одно число – минимальную стоимость, чтобы покрыть отрезок
[L, R]. Если покрыть отрезок [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