K. Kid's First Geometry Problem
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a convex polygon $$$A$$$ on the Cartesian plane. There are also $$$k$$$ more convex polygons $$$B_1, B_2, \dots, B_k$$$. Initially, for each $$$i = 1, 2, \dots, k$$$, the interiors of $$$A$$$ and $$$B_i$$$ intersect each other.

Your goal is to make $$$A$$$ not intersect any of $$$B_1, B_2, \dots, B_k$$$ (only boundaries touching is allowed). To achieve that, you can choose two real numbers $$$dx$$$ and $$$dy$$$ and translate the polygon $$$A$$$ by the vector $$$(dx, dy)$$$. The cost of doing this is $$$|dx| + |dy|$$$.

Find the minimum cost to achieve the goal.

Input

The first line contains an integer $$$n$$$ ($$$3 \le n \le 75000$$$), the number of vertices in $$$A$$$. Then $$$n$$$ lines follow. Each line contains two integers $$$x, y$$$ ($$$-10^8 \le x, y \le 10^8$$$) denoting the coordinates of a vertex of $$$A$$$.

The next line contains an integer $$$k$$$ ($$$1 \le k \le 25000$$$). Then the descriptions of $$$B_1, B_2, \dots, B_k$$$ follow. The description of $$$B_i$$$ starts with a line containing an integer $$$m_i$$$ ($$$3 \le m_i \le 75000$$$), the number of vertices in $$$B_i$$$. Then $$$m_i$$$ lines follow. Each line contains two integers $$$x, y$$$ ($$$-10^8 \le x, y \le 10^8$$$) denoting the coordinates of a vertex of $$$B_i$$$.

The vertices of each polygon are given in counterclockwise order, and no three vertices of the same polygon are collinear.

It is guaranteed that $$$\sum_{i=1}^k m_i \le 75000$$$.

Output

Print the minimum cost rounded up to the nearest integer. In other words, print the minimum integer that is not less than the answer.

Examples
Input
4
1 1
-1 1
-1 -1
1 -1
2
3
2 2
-2 2
-2 -2
3
2 -2
2 2
-2 2
Output
2
Input
5
0 0
1 0
2 1
1 2
0 1
3
4
-1 0
-1 -4
4 -4
4 1
4
0 0
2 0
2 3
0 3
4
1 4
-3 4
-3 -4
1 -4
Output
3
Note

The first example is shown in the diagram below. You can choose $$$(dx, dy) = (0, -2)$$$. The minimum cost is $$$2$$$.

In the second example, you can choose $$$(dx, dy) = (2, 0.8)$$$. The minimum cost is $$$2.8$$$, so you should output $$$3$$$.