CF366D Dima and Trap Graph

Dima and Inna love spending time together. The problem is, Seryozha isn't too enthusiastic to leave his room for some reason. But Dima and Inna love each other so much that they decided to get criminal... Dima constructed a trap graph. He shouted: "Hey Seryozha, have a look at my cool graph!" to get his roommate interested and kicked him into the first node. A trap graph is an undirected graph consisting of $ n $ nodes and $ m $ edges. For edge number $ k $ , Dima denoted a range of integers from $ l_{k} $ to $ r_{k} $ $ (l_{k}

The first line of the input contains two integers $ n $ and $ m $ $ (2

In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the $ n $ -th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes.

Explanation of the first example. Overall, we have 2 ways to get from node 1 to node 4: first you must go along the edge 1-2 with range \[1-10\], then along one of the two edges 2-4. One of them contains range \[3-5\], that is, we can pass through with numbers 3, 4, 5. So the loyalty of such path is 3. If we go along edge 2-4 with range \[2-7\], then we can pass through with numbers 2, 3, 4, 5, 6, 7. The loyalty is 6. That is the answer. The edge 1-2 have no influence on the answer because its range includes both ranges of the following edges.