Trò chơi đẩy bi

Trò chơi đẩy bi diễn ra trên một 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 $\dots, -3, -2, -1, 0, 1, 2, 3, \dots$ Các cột được đánh số từ trái sang phải, còn các dòng được đánh số từ dưới lên trên. Ô nằm tại giao điểm 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 xuất hiện trên lưới, mỗi viên bi chiếm đúng một ô và không có ô nào chứa nhiều hơn một viên bi. Người chơi phải chọn một ô tự do trên lưới để làm hố; nếu ô hố được chọn đang chứa bi, viên bi đó sẽ biến mất ngay lập tức. Ở 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 ô kề cạnh (hiện không chứa bi); nếu viên bi bị đẩy vào ô hố, viên bi đó sẽ biến mất. Nhiệm vụ của người chơi là đẩy toàn bộ các viên bi trên lưới vào 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 ô chứa bi, hãy chọn một ô tự do làm hố và tìm cách đẩy tất cả các viên bi trên lưới vào hố với số bước ít nhất.

Đầu vào:

• Dòng đầu tiên chứa số nguyên n là số lượng ô cấm.
• Dòng thứ $i$ $(i = 1, 2, \dots, n)$ trong n dòng tiếp theo chứa hai số nguyên $x_i, y_i$ mô tả ô $(x_i, y_i)$ là ô cấm.
• Dòng tiếp theo chứa số nguyên dương m là số lượng ô chứa bi.
• Dòng thứ $j$ $(j = 1, 2, \dots, m)$ trong m dòng tiếp theo chứa hai số nguyên $u_j, v_j$ mô tả ô $(u_j, v_j)$ là ô chứa bi.

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

Subtask (tham khảo)

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

Ví dụ 1:

Đầu vào:

1
2 2
2
1 2
3 2

Đầu ra:

4

Ví dụ 2:

Đầu vào:

0
2
1 1
5 5

Đầu ra:

8