Дима и Инна обожают проводить время вместе. Только Сережа почему-то не обожает уходить из собственной комнаты. Но Дима и Инна так любят друг друга, что решили пойти на криминал...
Дима сконструировал граф-ловушку и под предлогом: «Сереж, смотри какой у меня граф классный!», — толкнул соседа в первую вершину.
Граф-ловушка — это неориентированный граф, состоящий из n вершин и m ребер. Ребру с номером k Дима сопоставил диапазон целых чисел от lk до rk (lk ≤ rk). Чтобы выйти из графа ловушки, Сережа первоначально (перед началом пути) должен выбрать некоторое целое число (обозначим его x), после этого Сережа должен пройти путь от стартовой вершины с номером 1 до конечной вершины с номером n. При этом Сережа может пройти по ребру k только в том случае, если lk ≤ x ≤ rk.
Сережа — математик. Он определил лояльность какого-то пути из 1-ой вершины в n-ую, как количество целых чисел x, выбрав которые первоначально, можно пройти этот путь. Помогите Сереже найти путь, обладающий максимальной лояльностью, и поскорее вернуться в комнату!
Выходные данные
В единственной строке выходных данных выведите целое положительное число — максимальную лояльность, среди всех путей из первой вершины в n-ую. Если таких путей не существует, или максимальная лояльность равна 0, то в единственной строке выведите «Nice work, Dima!» без кавычек.
Примечание
Пояснение к примеру 1
У нас есть всего 2 способа попасть из вершины 1 в вершину 4: сперва нужно обязательно пройти по ребру 1-2 с диапазоном [1-10], затем, по одному из двух ребер 2-4.
Одно из них содержит диапазон [3-5], то есть мы можем пройти с числами 3, 4, 5. Лояльность такого пути — 3.
Если же идти по ребру 2-4 с диапазоном [2-7], то мы сможем пройти с числами 2, 3, 4, 5, 6, 7. Лояльность — 6. Это и есть ответ.
Ребро 1-2 не влияет на лояльность пути, так как его диапазон содержит в себе диапазоны следующих в пути ребер.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
|
6
|
|
2
|
5 6
1 2 1 10
2 5 11 20
1 4 2 5
1 3 10 11
3 4 12 10000
4 5 6 6
|
Nice work, Dima!
|