Traveling Plan

All submissions for this problem are available.
According to many researches, people can stand on a bus for several hours, but waiting for a bus for more than 30 minutes at a bus station can make us exhausted. The Chef is a perfect example for this fact. He always tries to reduce the longest period of time of waiting for a bus. Therefore, optimizing the traveling plan for him is far from an easy task.
Let's consider the bus system with N bus stations (numbered from 1 to N) and M buses (numbered from 1 to M). Each bus is represented by 4 integer numbers U, V, S, E which means it will start at the bus station U at the time S and arrive at the bus station V at the time E with no intermediate bus stations. If passenger arrives at the bus station U at the time X ≤ S, he has to wait for S − X units of time to catch this bus. Note, that if he arrives at the bus station U exactly at time S he can catch this bus with no waiting time.
The Chef starts at the time 0 in the bus station 1, and he wants to arrive at the bus station N in a way that the longest period that he spends for waiting for a bus is as small as possible. Besides, he must be at the bus station N before or at the time T for a specially important meeting. Note, that he may wait for a meeting if he arrives at the bus station N early but that period is not our concern here, since he doesn't wait for any bus at that time.
Input
The first line of the input contains three spaceseparated integers N, T and M, denoting the number of bus stations, the deadline for coming to bus station N and the number of buses, respectively. Each of the following M lines contains four spaceseparated integers U, V, S, E, the parameters of the current bus as described in the problem statement.
Output
If Chef cannot arrive at the bus station N before or at the time T, output 1. Otherwise, output the maximum period of time he has to wait for a bus in the optimal traveling 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}
Example
Input: 5 10 5 1 2 1 2 1 5 3 4 2 4 4 5 2 5 5 6 4 5 6 7 Output: 2
Explanation
There are three different traveling plans:
 bus 1 → bus 3 → bus 5. His waiting time for each bus is 1, 2, 1, respectively.
 bus 2. His waiting time is 3.
 bus 1 → bus 4. His waiting time for each bus is 1, 3, respectively.
For each traveling plan Chef arrives at the bus station N = 5 before the time T = 10. But only the first traveling plan is optimal, since the longest period of time his has to wait is 2.
Author:  tuananh93 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/TABUS 
Tags  binarysearch, cook32, dynamicprogramming, easymedium, graph, tuananh93 
Date Added:  26012013 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions