D. Дима и граф-ловушка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дима и Инна обожают проводить время вместе. Только Сережа почему-то не обожает уходить из собственной комнаты. Но Дима и Инна так любят друг друга, что решили пойти на криминал...

Дима сконструировал граф-ловушку и под предлогом: «Сереж, смотри какой у меня граф классный!», — толкнул соседа в первую вершину.

Граф-ловушка — это неориентированный граф, состоящий из n вершин и m ребер. Ребру с номером k Дима сопоставил диапазон целых чисел от lk до rk (lk ≤ rk). Чтобы выйти из графа ловушки, Сережа первоначально (перед началом пути) должен выбрать некоторое целое число (обозначим его x), после этого Сережа должен пройти путь от стартовой вершины с номером 1 до конечной вершины с номером n. При этом Сережа может пройти по ребру k только в том случае, если lk ≤ x ≤ rk.

Сережа — математик. Он определил лояльность какого-то пути из 1-ой вершины в n-ую, как количество целых чисел x, выбрав которые первоначально, можно пройти этот путь. Помогите Сереже найти путь, обладающий максимальной лояльностью, и поскорее вернуться в комнату!

Входные данные

Первая строка входных данных содержит два целых числа n и m (2 ≤ n ≤ 103, 0 ≤ m ≤ 3·103). Далее следует m строк, описывающих ребра. Каждая строка содержит четыре целых числа ak, bk, lk и rk (1 ≤ ak, bk ≤ n, 1 ≤ lk ≤ rk ≤ 106). Числа обозначают, что в графе-ловушке k-ое ребро соединяет вершины ak и bk, этому ребру сопоставлен диапазон целых чисел от lk до rk.

Обратите внимание, заданный граф может иметь петли и кратные ребра.

Выходные данные

В единственной строке выходных данных выведите целое положительное число — максимальную лояльность, среди всех путей из первой вершины в n-ую. Если таких путей не существует, или максимальная лояльность равна 0, то в единственной строке выведите «Nice work, Dima!» без кавычек.

Примеры
Входные данные
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
Выходные данные
6
Входные данные
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!
Примечание

Пояснение к примеру 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 не влияет на лояльность пути, так как его диапазон содержит в себе диапазоны следующих в пути ребер.