Даны \(n\) отрезков на числовой прямой, отрезки пронумерованы от \(1\) до \(n\). \(i\)-й отрезок покрывает все целочисленные точки от \(l_i\) до \(r_i\) и имеет значение \(w_i\).
Требуется выбрать поднабор этих отрезков (возможно, все). Когда набор выбран, разрешается перемещаться между двумя целочисленными точками, если существует выбранный отрезок, который накрывает обе точки. Поднабор называется хорошим, если возможно достичь точку \(m\), начав из точки \(1\), за произвольное количество ходов.
Цена поднабора — это разность между максимальным и минимальным значениями отрезков в нем. Найдите минимальную цену хорошего поднабора.
В каждом тесте существует хотя бы один хороший набор.
Выходные данные
Выведите одно целое число — минимальную цену хорошего поднабора.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3
|
3
|
|
2
|
1 10
1 10 23
|
0
|