## Travelling Danny

Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

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.

Input

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

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:

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.

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED