Zenyk, Cats and Chess
Limits: 2 sec., 256 MiB
Zenyk has two cats — Rudy and Pundyk. And Zenyk loves to play chess with them, but his cats are busy, so they can only play at a certain time: Pundyk at intervals [\(A_i\), \(B_i\)], and Rudy — [\(C_i\), \(D_i\)].
Zenyk can switch to playing with another cat at any time (not necessarily at whole moments), but cannot play with two cats at the same time. Also, if \(A_i + 1\) = \(B_i\), it means that a cat can play chess for exactly one unit of time.
Zenyk wants to calculate the maximum total playing time with both cats, as well as the minimum absolute difference between the playing time with Rudy and Pundyk at the maximum total time. Unfortunately, he can’t do it himself, so he asks you to help.
Input
In the first line, there is one integer \(N\) — the number of time segments when Rudy can play chess.
In the next \(N\) lines, there are two integers \(A_i\), \(B_i\) separated by space — they mean that Rudy can play from \(A_i\) to \(B_i\) inclusive.
In the next line, there is one integer \(M\) — the number of time segments when Pundyk can play chess.
In the following \(M\) lines, there are two integers \(C_i\), \(D_i\) separated by space — intervals of time when Pundyk can play chess.
The time intervals for each of the cats separately do not intersect.
Output
Print two integers separated by space — the maximum total playing time with cats and the minimum time difference between playing with Rudy and Pundyk.
We can show that correct answer will contain two integers.
Constraints
\(1 \le N, M \le 3\cdot 10^{5}\),
\(1 \le A_i, B_i, C_i, D_i \le 10^{9}\),
\(A_i < B_i\),
\(C_i < D_i\).
Samples
Input (stdin) | Output (stdout) |
---|---|
1 2 7 1 1 3 | 6 2 |
Input (stdin) | Output (stdout) |
---|---|
1 1 3 1 2 4 | 3 0 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|