Mô tả đề bài

Trò chơi đẩy bi là một trò chơi trên lưới ô vuông vô hạn. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng ~x~ và cột ~y~ được gọi là ô ~(x, y)~. Trên lưới có một số ô cấm, các ô còn lại là tự do. Khi bắt đầu trò chơi, một số viên bi sẽ xuất hiện trên lưới, mỗi viên bi sẽ nằm gọn trong một ô và không có ô nào chứa nhiều hơn một viên bi. Người chơi sẽ phải chọn một ô tự do trên lưới để làm cái hố, nếu ô được chọn làm cái hố có chứa bi thì viên bi đó sẽ biến mất. Ở mỗi bước, người chơi có thể chọn một ô chứa bi và đẩy viên bi đó sang một trong bốn ô chung cạnh (hiện đang không có bi), nếu viên bi bị đẩy vào cái hố thì viên bi này sẽ biến mất. Nhiệm vụ của người chơi là đẩy hết tất cả các viên bi trên lưới vào cái hố với số bước ít nhất. Yêu cầu: Cho biết vị trí các ô cấm trên lưới và vị trí các ô có chứa bi. Hãy chọn một ô tự do làm cái hố và tìm cách đẩy tất cả các viên bi trên lưới vào cái hố với số bước ít nhất.

Input format

• Dòng thứ nhất ghi số nguyên dương ~n~ là số ô cấm.
• Dòng thứ ~i (i = 1, 2, …, n)~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i, y_i~ mô tả ô ~(x_i, y_i)~ là ô cấm.
• Dòng tiếp theo ghi số nguyên dương ~m~ là số ô chứa bi.
• Dòng thứ ~j (j = 1, 2, …, m)~ trong ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_j, v_j~ mô tả ô ~(u_j, v_j)~ là ô chứa bi.

Output format

In ra một số nguyên là số bước ít nhất cần thiết để đẩy tất cả các viên bi trên lưới vào cái hố. In ra ~-1~ nếu không tồn tại cách chọn cái hố để đẩy hết tất cả các viên bi trên lưới vào hố.

Sample Input 1

1
2 2
2
1 2
3 2

Sample Output 1

4

Sample Input 2

0
2
1 1
5 5

Sample Output 2

8

Subtasks

• Có ~15\%~ số lượng test thỏa mãn điều kiện: ~n = 0, m = 2~ và các số ~u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~15\%~ số lượng test khác thỏa mãn điều kiện: ~n = 1, m = 2~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n = 0, m \leq 100~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 1000, m \leq 100~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~30\%~ số lượng test còn lại thỏa mãn điều kiện: ~n = 0, m \leq 100~ và các số ~u_j, v_j~ là số nguyên dương không vượt quá ~10^9~;