407668: GYM102868 F Red

Red has gone by the admin table a few times to try to figure out where the rest of the crewmates are. From the admin table, she can view the number of people in the rooms across the ship. Red has a list of observations that include both the time of observation and the number of people Red saw in rooms at the time.

After the rest of the crewmates meet up to figure out what happened since the last meeting, each crewmate gives a series of time intervals where they were in a room that the admin table tracks. As the one responsible for manning the admin table, Crewmate Red must be able to run through these time intervals and figure out if there's some inconsistency between the number of people who say that they're in rooms and what was actually observed by the admin panel. Given the observations and time intervals, figure out the earliest time where there's an inconsistency between the number of people who claim that they're in rooms and the admin table observations. If there are no inconsistencies, output $$$-1$$$.

The first line will consist of two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^4)$$$, which give the number of time intervals given by crewmates and the number of observations on the admin table, respectively. The next $$$n$$$ lines consist of two integers $$$l_i, r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10^{18})$$$, which means that a crewmate claims to be in a room detected by the admin table for all times on the inclusive interval $$$[l_i, r_i]$$$. The next $$$q$$$ lines consist of two integers $$$t_i, v_i$$$ $$$(1 \leq t_i \leq 10^{18}, 0 \leq v_i \leq 10^{18})$$$, which gives an admin table observation at time $$$t_i$$$ where Red saw $$$v_i$$$ people in rooms.

Output a single integer, which gives the earliest time where Red saw an inconsistency between the claimed intervals and her observations.

3 5
2 4
5 6
1 4
1 1
5 0
3 2
2 2
6 1

5

3 3
2 4
5 6
1 4
1 1
6 1
8 0

-1

For the first input, the number of people in the rooms at times $$$[1, 6]$$$ are $$$[1, 2, 2, 2, 1, 1]$$$ according to the given time intervals. The first inconsistency is at time $$$5$$$, where the admin table observation gives $$$0$$$ people, but the number of people according to the crewmate intervals is $$$1$$$. For the second input, there are no inconsistencies.