Săn Kho Báu

Bạn đang ở trên một hòn đảo được biểu diễn bởi một lưới $n\times m$. Các hàng được đánh số từ $1$ đến $n$, các cột từ $1$ đến $m$. Trên đảo có $k$ kho báu, kho báu thứ $i$ nằm tại ô $(r_i,c_i)$.

Ban đầu bạn đứng ở góc dưới bên trái của lưới, tức ô $(1,1)$. Nếu tại bất kỳ thời điểm nào bạn đứng trên một ô chứa kho báu, bạn nhặt nó mà không tốn thêm thời gian. Trong một bước di chuyển, bạn có thể đi lên (từ $(r,c)$ sang $(r+1,c)$), trái (từ $(r,c)$ sang $(r,c-1)$), hoặc phải (từ $(r,c)$ sang $(r,c+1)$). Vì bẫy, bạn không thể đi xuống.

Tuy nhiên, đi lên cũng rất nguy hiểm. Bạn chỉ có thể đi lên khi đang ở một cột an toàn. Có $q$ cột an toàn: $b_1,b_2,\dots ,b_q$.

Hãy tính số bước di chuyển tối thiểu để thu thập tất cả các kho báu.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n,m,k,q$ — số hàng, số cột, số kho báu và số cột an toàn.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r_i,c_i$ — tọa độ ô chứa kho báu thứ $i$. Các kho báu nằm ở các ô phân biệt.
• Dòng cuối cùng chứa $q$ số nguyên phân biệt $b_1,b_2,\dots ,b_q$ — các cột an toàn.

Dữ liệu ra

In ra số bước di chuyển tối thiểu để thu thập tất cả các kho báu.

Ràng buộc

• $2\le n,m,k,q\le 2·{10}^5$
• $q\le m$
• $1\le r_i\le n$, $1\le c_i\le m$
• $1\le b_i\le m$, các $b_i$ phân biệt.

Ví dụ