Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
107 - ZOJ Monthly, July 2011 - I
Unsafe Factor

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Xiao Ming has two paper tapes with the same length. He wants to use them to hang some weight. But XiaoMing finds that the paper tape may have some damaged areas, which will make the tape easier to be broken. For clever Xiao Ming, he sticks these two tapes up from the start point to the end point.

But there is a new problem, after paste, in some place the tape may exist hidden flaw. Hidden flaw means at this place, one of the two tape has damaged areas before paste, but after paste, this kind of damaged areas may be difficult to be found, otherwise, if both of the tapes at some places have damaged areas, they are still visible after pasting.

After this paste work, his father goes back home and finds XiaoMing's perfect work. His father finds damaged areas which are still visible on the new tape and fixs it. Oh, what an adorable father he is!

Because of the hidden damaged areas, there is still unsafe factor. We define the "Unsafe Factor" as the longest length of the successive hidden damaged areas.

Your task is to calculate the "Unsafe Factor".

NOTICE: the damaged areas are regarded as a point on the tape.

Input

The input file contains several test cases (no more than 20).

For each case, the first line contains three integers L, n1, n2 (0 < L ≤ 10000000, 0 ≤ n1, n2 ≤ 100000) which indicate the length of the tape, the number of the damaged area intervals for tape 1 and the number of the damaged area intervals for tape 2. Then follows n1 and n2 lines. The format of each line is two integer "x y" (0 ≤ x ≤ y < L), indicate there are damaged areas at x to y (x, x+1, x+2, x+3, ... y point have a damaged area).

We ensure that each damaged area is told only once in the input file for each case.

Output

For each case, output the "Unsafe Factor" in a single line.

Sample Input

10 3 2
1 4
5 6
8 9
1 1
6 7

Sample Output

4

Hint

Because of huge input, scanf is recommended.


Author: LI, Fei
Contest: ZOJ Monthly, July 2011
Submit    Status