According to many researches, people can stand on a bus for several hours, but w
ID: 3539736 • Letter: A
Question
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 %u2264 S, he has to wait for S %u2212 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.
The first line of the input contains three space-separated 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 space-separated integers U, V, S, E, the parameters of the current bus as described in the problem statement.
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.
There are three different traveling plans:
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.