G. Anti-Gravity Boots
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga is trying to escape Michael. Initially, he starts at position $$$1$$$. In front of him, there are a series of platforms on which he can stand. Some of the platforms are on the ceiling, others on the floor. He cannot stand on empty space (and will fall and die if he does). While running, he can turn on and off his anti-gravity boots which instantaneously flip his orientation, allowing him to walk on the ceiling platforms. His anti-gravity boots can be activated as much as Gunga wants.

Note: the anti-gravity boots will flip Gunga, but during this period Gunga will not move forward any blocks.

Given the starting position and length of each platform on the ceiling and the floor, determine the farthest position Gunga can reach.

Input

The first line contains two single integers $$$n,m$$$ $$$(1\le n,m\le 10^5)$$$ - the number of platforms on the floor and on the ceiling.

The next $$$n$$$ lines contain two integers $$$a_i,b_i$$$ $$$(1\le a_i,b_i\le 10^9)$$$ - the starting position of the $$$i$$$-th platform and its length, which means that it spans the segment $$$[a_i,a_i+b_i-1]$$$.

The next $$$m$$$ lines contain two integers $$$c_i,d_i$$$ $$$(1\le c_i,d_i\le 10^9)$$$ - the starting position of the $$$i$$$-th platform and its length, which means that it spans the segment $$$[c_i,c_i+d_i-1]$$$ on the ceiling.

It's guaranteed that no two floor platforms overlap. Similarly, no two ceiling platforms overlap.

Output

A single line containing the farthest position Gunga can reach.

Example
Input
2 3
4 2
1 2
5 10
2 3
100 5
Output
14
Note

In the first example, Gunga can move to position 2 on the platform on the floor, then switch to the ceiling and move to position 4. Then switch back to the floor and move to position 5. Finally, he can switch to the ceiling again and move to position 14.