Trò chơi đẩy bi

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 $\dots ,-3,-2,-1,0,1,2,3,\dots$ Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng được đánh số 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 nằm gọn trong một ô tự do 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 ô được chọn làm ô 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, với điều kiện ô đó là ô tự do và hiện đang không có bi (viên bi không bao giờ được đẩy vào ô cấm). Nếu viên bi bị đẩy vào ô 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 hố với số bước ít nhất.

Ô hố có thể là bất kỳ ô tự do nào của lưới vô hạn, kể cả ô nằm ngoài phạm vi tọa độ xuất hiện trong dữ liệu vào.

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 ô 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.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên không âm $n$ là số ô 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 ghi số nguyên dương $m$ là số ô 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.

Các ô cấm đôi một khác nhau, các ô chứa bi đôi một khác nhau và không có ô chứa bi nào là ô cấm.

Dữ liệu ra

Một dòng chứa 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 hố. Ghi $-1$ nếu không tồn tại cách chọn hố để đẩy hết tất cả các viên bi trên lưới vào hố.

Ràng buộc

• $0\le n\le 1000$, $1\le m\le 100$.
• Nếu $n\ge 1$ thì mọi $x_i,y_i,u_j,v_j$ là số nguyên dương không vượt quá $100$.
• Nếu $n=0$ thì $\left|u_j\right|,\left|v_j\right|\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n=0$, $m=2$ và các số $u_j,v_j$ là số nguyên dương không vượt quá $100$.
• Subtask 2 ($20\%$ số điểm): $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$.
• Subtask 3 ($20\%$ số điểm): $n=0$, $m\le 100$ và các số $u_j,v_j$ là số nguyên dương không vượt quá $100$.
• Subtask 4 ($20\%$ số điểm): $n\le 1000$, $m\le 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$.
• Subtask 5 ($20\%$ số điểm): $n=0$, $m\le 100$ và các số $u_j,v_j$ là số nguyên có giá trị tuyệt đối không vượt quá ${10}^9$.

Ví dụ