A working window spans positions 0 to day (inclusive of 0, exclusive of day). Several busy intervals, each a half-open [start, end) lying inside [0, day], block off time. A meeting needs a free slot of length exactly need, i.e. an interval [t, t + need) that overlaps no busy interval and stays within [0, day]. Report the smallest such start time t, or -1 if no free slot of that length exists.
Input format
Line 1: two integers day and need.
Line 2: an integer m, the number of busy intervals.
Next m lines: two integers start end (with 0 <= start < end <= day).
Output format
A single integer: the earliest valid start time, or -1 if none exists.
Constraints
- 1 ≤ day ≤ 1000000
- 1 ≤ need ≤ 1000000
- 0 ≤ m ≤ 100000
- Busy intervals may be given in any order and may overlap.