Daenerys Targaryen is on her quest to claim the Great Iron Throne.On her way to King's Landing there are N small regions where she can stay.She wants to reach King's Landing as soon as possible.But her horses are very stubborn.Each horse is represented by 4 integers u,v,s,e. It will start from region u at time s and arrive at region v at time e without stopping at intermediate regions.It will stop at region v and won't go further.So Danny would have to wait for another horse to take her ahead.If she reaches at a region u at time x<=s, she would have to wait for s-x units of time.If she arrives at region at exactly time s then she can take the horse immediately. She starts at time 0 from Valerys(1) and arrives at Kings Landing (N) in a way that longest period she spends for waiting for horse is minimum.But she has to reach Kings Landing (N) before or at time T as only then she can claim the Throne.So help Danny in reaching there.
The first line of the input contains three space-separated integers N, T and M, denoting the number of regions, the deadline for coming to region N (Kings Landing) and the number of horses respectively. Each of the following M lines contains four space-separated integers U, V, S, E, the parameters of the current horse as described in the problem statement. Output If Danny cannot arrive at Kings Landing N before or at the time T, output -1. Otherwise, output the maximum period of time she has to wait for a horse in the optimal plan.
Constraints 2 â‰¤ N â‰¤ 50000 1 â‰¤ T â‰¤ 10^9 1 â‰¤ M â‰¤ 100000 (10^5) 1 â‰¤ U â‰¤ N 1 â‰¤ V â‰¤ N U â‰ V 0 â‰¤ S < E â‰¤ 10^9
There are three different traveling plans: horse 1 â†’ horse 3 â†’ horse 5. Her waiting time for each horse is 1, 2, 1, respectively. horse 2. Her waiting time is 3. horse 1 â†’ horse 4. Her waiting time for each horse is 1, 3, respectively. For each traveling plan Danny arrives at the region N = 5 before the time T = 10. But only the first plan is optimal, since the longest period of time she has to wait is 2.