Twin-Chamber Certification Run

An aerospace test lab certifies a prototype using two rooms: a Wind-Tunnel Chamber and a Pressure Chamber. You must run exactly one certification test in the Wind-Tunnel Chamber and exactly one in the Pressure Chamber. You can only be inside one chamber at a time, but you may choose to run either chamber's test first.

You are given n candidate test slots for the Wind-Tunnel Chamber and m candidate test slots for the Pressure Chamber. Wind-Tunnel slot i has an earliest eligible start time wStart[i] and a fixed duration wDur[i]; Pressure Chamber slot j has an earliest eligible start time pStart[j] and a fixed duration pDur[j]. You start free at time 0. If you are free at time t and you choose to run a slot with earliest eligible start s and duration d, you actually begin at time max(t, s) (waiting if you arrive before the slot opens) and you finish at max(t, s) + d.

Choose exactly one Wind-Tunnel slot, exactly one Pressure Chamber slot, and an order (Wind-Tunnel first or Pressure Chamber first) so that the time at which you finish BOTH tests is as small as possible. Report that minimum possible finish time.

Input format

• Line 1: two integers n and m
• Next n lines: two integers wStart[i] and wDur[i], one Wind-Tunnel Chamber slot per line
• Next m lines: two integers pStart[j] and pDur[j], one Pressure Chamber slot per line

Output format

• A single integer: the minimum possible time by which both tests can be finished.

Constraints

• 1 <= n, m <= 200
• 1 <= wStart[i], wDur[i], pStart[j], pDur[j] <= 1000

2 2
1 3
4 2
2 4
5 1

6

1 1
5 2
1 1

7