You are on the island which can be represented as a $n \times m$ table. The rows are numbered from $1$ to $n$ and the columns are numbered from $1$ to $m$. There are $k$ treasures on the island, the $i$-th of them is located at the position $(r_i, c_i)$.

Initially you stand at the lower left corner of the island, at the position $(1, 1)$. If at any moment you are at the cell with a treasure, you can pick it up without any extra time. In one move you can move up (from $(r, c)$ to $(r+1, c)$), left (from $(r, c)$ to $(r, c-1)$), or right (from position $(r, c)$ to $(r, c+1)$). Because of the traps, you can't move down.

However, moving up is also risky. You can move up only if you are in a safe column. There are $q$ safe columns: $b_1, b_2, \ldots, b_q$. You want to collect all the treasures as fast as possible. Count the minimum number of moves required to collect all the treasures.


-----Input-----

The first line contains integers $n$, $m$, $k$ and $q$ ($2 \le n, \, m, \, k, \, q \le 2 \cdot 10^5$, $q \le m$) — the number of rows, the number of columns, the number of treasures in the island and the number of safe columns.

Each of the next $k$ lines contains two integers $r_i, c_i$, ($1 \le r_i \le n$, $1 \le c_i \le m$) — the coordinates of the cell with a treasure. All treasures are located in distinct cells.

The last line contains $q$ distinct integers $b_1, b_2, \ldots, b_q$ ($1 \le b_i \le m$) — the indices of safe columns.


-----Output-----

Print the minimum number of moves required to collect all the treasures.


-----Examples-----
Input
3 3 3 2
1 1
2 1
3 1
2 3

Output
6
Input
3 5 3 2
1 2
2 3
3 1
1 5

Output
8
Input
3 6 3 2
1 6
2 2
3 4
1 6

Output
15


-----Note-----

In the first example you should use the second column to go up, collecting in each row treasures from the first column. [Image] 

In the second example, it is optimal to use the first column to go up. [Image] 

In the third example, it is optimal to collect the treasure at cell $(1;6)$, go up to row $2$ at column $6$, then collect the treasure at cell $(2;2)$, go up to the top row at column $1$ and collect the last treasure at cell $(3;4)$. That's a total of $15$ moves. [Image]

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n,m,k,q=list(map(int,input().split()))
TR=[list(map(int,input().split())) for i in range(k)]
SAFE=list(map(int,input().split()))
SAFE.sort()

TRLIST=[[] for i in range(n+1)]

for x,y in TR:
    TRLIST[x].append(y)

while TRLIST[-1]==[]:
    TRLIST.pop()
    n-=1


START={1:0} #place,step

import bisect

for step in range(1,n):
    if TRLIST[step]==[] and step!=1:
        continue
    elif TRLIST[step]==[] and step==1:
        MIN=MAX=1
    else:
        MIN=min(TRLIST[step])
        MAX=max(TRLIST[step])

    MINind=max(0,bisect.bisect_left(SAFE,MIN)-1)
    MIN_L=SAFE[MINind]
    if MINind==q-1:
        MIN_R=MIN_L
    else:
        MIN_R=SAFE[MINind+1]

    MAXind=max(0,bisect.bisect_left(SAFE,MAX)-1)
    MAX_L=SAFE[MAXind]
    if MAXind==q-1:
        MAX_R=MAX_L
    else:
        MAX_R=SAFE[MAXind+1]
    

    NEXT=dict()

    for start in START:
        st=START[start]
        
        NEXT[MIN_L]=min(st+abs(MAX-start)+abs(MAX-MIN)+abs(MIN_L-MIN),NEXT.get(MIN_L,1<<50))
        NEXT[MIN_R]=min(st+abs(MAX-start)+abs(MAX-MIN)+abs(MIN_R-MIN),NEXT.get(MIN_R,1<<50))
        NEXT[MAX_L]=min(st+abs(MIN-start)+abs(MAX-MIN)+abs(MAX_L-MAX),NEXT.get(MAX_L,1<<50))
        NEXT[MAX_R]=min(st+abs(MIN-start)+abs(MAX-MIN)+abs(MAX_R-MAX),NEXT.get(MAX_R,1<<50))

    START=NEXT
    #print(START)

LAST=1<<50

if TRLIST[n]==[]:
    print(min(START.values())+n-1)
    return

MIN=min(TRLIST[n])
MAX=max(TRLIST[n])
#print(START)
for start in START:
    st=START[start]
    
    LAST=min(LAST,st+abs(MAX-start)+abs(MAX-MIN),st+abs(MIN-start)+abs(MAX-MIN))


print(LAST+n-1)

    
    


import sys

n, m, k, q = list(map(int, sys.stdin.readline().strip().split()))
T = [0] * k
for i in range (0, k):
    T[i] = list(map(int, sys.stdin.readline().strip().split()))
    T[i][1] = T[i][1] - 1
    T[i][0] = T[i][0] - 1
T.sort() # treasures sorted by row
b = list(map(int, sys.stdin.readline().strip().split()))
b.sort()
for i in range (0, q):
    b[i] = b[i] - 1     # sorted safe columns
L = [b[0]] * m          # safe column left
R = [b[-1]] * m         # safe column right
R1 = [10 ** 6] * n      # leftmost treasure
R2 = [-1] * n           # rightmost treasure
n1 = 0                  # pathlength 1
n2 = 0                  # pathlength 2
for i in range (0, k):
    R1[T[i][0]] = min(R1[T[i][0]], T[i][1])
    R2[T[i][0]] = max(R2[T[i][0]], T[i][1])
for i in range (0, q):
    L[b[i]] = b[i]
    R[b[i]] = b[i]
for i in range (1, m):
    L[i] = max([L[i-1], L[i]])
    R[m-i-1] = min([R[m-i], R[m-i-1]])
r = 0
c1 = 0
c2 = 0
n1 = 0
n2 = 0
if R2[0] != -1:
    c1 = R2[0]
    c2 = R2[0]
    n1 = R2[0]
    n2 = R2[0]
for i in range (1, n):
    if R2[i] != -1:
        r, c1, c2, n2, n1 = i, R1[i], R2[i], i-r+abs(R1[i]-R2[i])+min([n1+abs(c1-L[c1])+abs(R1[i]-L[c1]), n2+abs(c2-L[c2])+abs(R1[i]-L[c2]), n1+abs(c1-R[c1])+abs(R1[i]-R[c1]), n2+abs(c2-R[c2])+abs(R1[i]-R[c2])]), i-r+abs(R1[i]-R2[i])+min([n1+abs(c1-L[c1])+abs(R2[i]-L[c1]), n2+abs(c2-L[c2])+abs(R2[i]-L[c2]), n1+abs(c1-R[c1])+abs(R2[i]-R[c1]), n2+abs(c2-R[c2])+abs(R2[i]-R[c2])])
print(min([n1, n2]))


bn = 0
ar = []
def  binSearchMax(number):
    last = bn
    first = 0
    mid = (last + first) // 2
    while(last >= first):
        if(ar[mid] < number):
            first = mid + 1
        elif(ar[mid] > number):
            last = mid - 1
        else:
            return mid
        mid = (last + first) // 2
    if (ar[last] == number):
        return last
    return first

n, m, k, q = list(map(int,input().split()))
mmn = [[m,-1] for i in range(n)]
maxn = 0
for i in range(k):
    r, c = list(map(int,input().split()))
    r -= 1
    mmn[r][0] = min(mmn[r][0],c)
    mmn[r][1] = max(mmn[r][1],c)
    maxn = max(maxn,r)
if mmn[0][1] == -1:
    mmn[0][1] = 1
mmn[0][0] = 1
bi = list(map(int,input().split()))
bi += [-1000000000, 10000000000, -1000000000, 10000000000, 10000000000]
bi.sort()
ar = bi
bn = q + 3
dp = [[0,0] for i in range(n)]

dp[0][1] = mmn[0][1] - mmn[0][0]
dp[0][0] = dp[0][1] * 2
z = 0
for i in range(1,n):
    if mmn[i][1] == -1:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1] 
        continue
    p1 = binSearchMax(mmn[z][0])
    p2 = bi[p1-1]
    p1 = bi[p1]
    p3 = binSearchMax(mmn[z][1])
    p4 = bi[p3-1]
    p3 = bi[p3]
    num1 = abs(p1 - mmn[i][1]) + abs(p1 - mmn[z][0]) + dp[z][0]
    num2 = abs(p2 - mmn[i][1]) + abs(p2 - mmn[z][0]) + dp[z][0]
    num3 = abs(p3 - mmn[i][1]) + abs(p3 - mmn[z][1]) + dp[z][1]
    num4 = abs(p4 - mmn[i][1]) + abs(p4 - mmn[z][1]) + dp[z][1] 
    dp[i][0] = min(min(num1,num2),min(num3,num4)) + mmn[i][1] - mmn[i][0]
    num1 = abs(p1 - mmn[i][0]) + abs(p1 - mmn[z][0]) + dp[z][0]
    num2 = abs(p2 - mmn[i][0]) + abs(p2 - mmn[z][0]) + dp[z][0]
    num3 = abs(p3 - mmn[i][0]) + abs(p3 - mmn[z][1]) + dp[z][1]
    num4 = abs(p4 - mmn[i][0]) + abs(p4 - mmn[z][1]) + dp[z][1]
    dp[i][1] = min(min(num1,num2),min(num3,num4)) + mmn[i][1] - mmn[i][0]
    z = i
print(min(dp[-1]) + maxn)


def lsearch(arr, v):
    if arr[0] > v:
        return None
    l = 0
    r = len(arr) - 1
    while (r-l>1):
        m = (l+r)//2
        if arr[m] > v:
            r = m
        else:
            l = m
    if arr[r] <= v:
        return arr[r]
    return arr[l]


def rsearch(arr, v):
    if arr[-1] < v:
        return None
    l = 0
    r = len(arr) - 1
    while (r-l>1):
        m = (l+r)//2
        if arr[m] >= v:
            r = m
        else:
            l = m
    if arr[l] >= v:
        return arr[l]
    return arr[r]


def lcost(start, s, b):
    l = lsearch(b, start)
    r = rsearch(b, start)
    if l is None:
        l = r
    if r is None:
        r = l
    vl = abs(start-l) + abs(s[-1]-l) + abs(s[0]-s[-1])
    vr = abs(start-r) + abs(s[-1]-r) + abs(s[0]-s[-1])
    return min(vl, vr)


def rcost(start, s, b):
    l = lsearch(b, start)
    r = rsearch(b, start)
    if l is None:
        l = r
    if r is None:
        r = l
    vl = abs(start-l) + abs(s[0]-l) + abs(s[0]-s[-1])
    vr = abs(start-r) + abs(s[0]-r) + abs(s[0]-s[-1])
    return min(vl, vr)



n, m, k, q = map(int, input().split())
ss = [[] for _ in range(n)]
for _ in range(k):
    r, c = map(int, input().split())
    ss[r-1].append(c-1)

bs = list(map(lambda x: int(x)-1, input().split()))
bs.sort()

for row in ss:
    row.sort()

lc = 0
rc = 0
l = 0
r = 0
if ss[0]:
    l = ss[0][-1]
    r = ss[0][-1]
    lc = rc = l
top = 0
for ind, s in enumerate(ss[1:]):
    if s:
        nlc = min(lcost(l, s, bs)+lc, lcost(r, s, bs)+rc)
        nrc = min(rcost(l, s, bs)+lc, rcost(r, s, bs)+rc)
        lc = nlc
        rc = nrc
        l = s[0]
        r = s[-1]
        top = ind+1

res = min(lc, rc) + top
print(res)

import bisect

n, m, k, q = map(int, input().split())

# min, max
vals = {}
vals[1] = [1, 1]
for i in range(k):
	r, c = map(int, input().split())
	if r not in vals:
		vals[r] = [c, c]
	else:
		vals[r][0] = min(vals[r][0], c)
		vals[r][1] = max(vals[r][1], c)

q = list(map(int, input().split()))
q.sort()

def find_shortest(lower, upper, row):
	if row==1:
		return upper-1

	if lower > upper:
		return find_shortest(upper, lower, row)

	pos = bisect.bisect_left(q, lower)
	options = []
	if pos < len(q):
		if q[pos]<=upper:
			return upper-lower
		else:
			options.append(q[pos] - lower + q[pos] - upper)
	

	pos2 = bisect.bisect_left(q, lower) - 1
	if pos2 >= 0:
		options.append(lower - q[pos2] + upper - q[pos2])
	return min(options)

highest = 1
old_a, old_b = 0, 0
pos_a, pos_b = 1, 1
for row in range(1, n+1):
	if not row in vals:
		continue
	highest = row
	row_min, row_max = vals[row]

	new_a = min(old_a + find_shortest(pos_a, row_max, row), old_b + find_shortest(pos_b, row_max, row)) + row_max - row_min
	new_b = min(old_a + find_shortest(pos_a, row_min, row), old_b + find_shortest(pos_b, row_min, row)) + row_max - row_min

	old_a, old_b = new_a, new_b
	pos_a, pos_b = row_min, row_max
	#print(old_a, old_b)

total = highest - 1
total += min(old_a, old_b)

print(total)

# see bisect module:
# https://codeforces.com/contest/1201/submission/58302708

# python complexity:
# https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

# solve using DP

n, m, k, q = map(int, input().split())
# n rows
# m cols

tr_min = [None for _ in range(n)]
tr_max = [None for _ in range(n)]
for _ in range(k):
    row, col = map(int, input().split())
    row = n - row
    col -= 1
    if tr_min[row] == None or col < tr_min[row]:
        tr_min[row] = col
    if tr_max[row] == None or col > tr_max[row]:
        tr_max[row] = col
tr_min[-1] = 0
tr_max[-1] = tr_max[-1] or 0

savecols = sorted(map(lambda t: int(t) - 1, input().split()))
# binary search? :)
def binsearch(arr, val):
    l, r = 0, len(arr)-1
    while l <= r:
        mid = l + (r - l) // 2
        if (arr[mid] < val):
            l = mid + 1
        elif (arr[mid] > val):
            r = mid - 1
        else:
            return mid

    return r
    

def find_short_descent(A, B):
    if A > B:
        return find_short_descent(B, A) # this is invariant

    idx1 = binsearch(savecols, A)
    idx2 = idx1 + 1
    minval = m*m
    if idx2 < len(savecols):
        if savecols[idx2] < B:
            return B - A
        else:
            minval = min(minval, (savecols[idx2] << 1) - A - B)

    if idx1 >= 0:
        minval = min(minval, A + B - (savecols[idx1] << 1))
    return minval



l, r = 0, 0
found_valid = False
last_valid = None
for row in range(0, n):
    #insert idea here
    if found_valid == False:
        if tr_min[row] != None:
            found_valid = True
            last_valid = row
            l = (tr_max[row] - tr_min[row])
            r = (tr_max[row] - tr_min[row])
            continue
        continue
    
    if tr_min[row] == None:
        l += 1
        r += 1
        continue

    ll = find_short_descent(tr_min[last_valid], tr_min[row])
    lr = find_short_descent(tr_min[last_valid], tr_max[row])
    rl = find_short_descent(tr_max[last_valid], tr_min[row])
    rr = find_short_descent(tr_max[last_valid], tr_max[row])
        
    #l += min(ll, rl) + 1 + (tr_max[row] - tr_min[row])
    #r += min(lr, rr) + 1 + (tr_max[row] - tr_min[row])
    #l, r = r, l
    new_l = min(l + lr, r + rr) + 1 + (tr_max[row] - tr_min[row])
    new_r = min(l + ll, r + rl) + 1 + (tr_max[row] - tr_min[row])
    l, r = new_l, new_r
    last_valid = row

# insert last step on row n here
answ = l + tr_min[last_valid]
print(answ)

# see bisect module:
# https://codeforces.com/contest/1201/submission/58302708

# python complexity:
# https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

# solve using DP

n, m, k, q = map(int, input().split())
# n rows
# m cols

tr_min = [None for _ in range(n)]
tr_max = [None for _ in range(n)]
for _ in range(k):
    row, col = map(int, input().split())
    row = n - row
    col -= 1
    if tr_min[row] == None or col < tr_min[row]:
        tr_min[row] = col
    if tr_max[row] == None or col > tr_max[row]:
        tr_max[row] = col
tr_min[-1] = 0
tr_max[-1] = tr_max[-1] or 0

savecols = sorted(map(lambda t: int(t) - 1, input().split()))
# binary search? :)
def binsearch(arr, val):
    l, r = 0, len(arr)-1
    while l <= r:
        mid = l + (r - l) // 2
        if (arr[mid] < val):
            l = mid + 1
        elif (arr[mid] > val):
            r = mid - 1
        else:
            return mid

    return r
    

def find_short_descent(A, B):
    if A > B:
        return find_short_descent(B, A) # this is invariant

    idx1 = binsearch(savecols, A)
    idx2 = idx1 + 1
    minval = 2 * m # for both directions
    if idx2 < len(savecols):
        if savecols[idx2] < B:
            return B - A
        else:
            minval = min(minval, (savecols[idx2] << 1) - A - B)

    if idx1 >= 0:
        minval = min(minval, A + B - (savecols[idx1] << 1))
    return minval



l, r = 0, 0
found_valid = False
last_valid = None
for row in range(0, n):
    #insert idea here
    if found_valid == False:
        if tr_min[row] != None:
            found_valid = True
            last_valid = row
            l = (tr_max[row] - tr_min[row])
            r = (tr_max[row] - tr_min[row])
            continue
        continue
    
    if tr_min[row] == None:
        l += 1
        r += 1
        continue

    ll = find_short_descent(tr_min[last_valid], tr_min[row])
    lr = find_short_descent(tr_min[last_valid], tr_max[row])
    rl = find_short_descent(tr_max[last_valid], tr_min[row])
    rr = find_short_descent(tr_max[last_valid], tr_max[row])
        
    #l += min(ll, rl) + 1 + (tr_max[row] - tr_min[row])
    #r += min(lr, rr) + 1 + (tr_max[row] - tr_min[row])
    #l, r = r, l
    new_l = min(l + lr, r + rr) + 1 + (tr_max[row] - tr_min[row])
    new_r = min(l + ll, r + rl) + 1 + (tr_max[row] - tr_min[row])
    l, r = new_l, new_r
    last_valid = row

# insert last step on row n here
answ = l + tr_min[last_valid]
print(answ)

from bisect import *

n, m, k, q = list(map(int, input().split()))
right = [-1] * n
left = [-1] * n
for i in range(k):
    row, col = list(map(int, input().split()))
    row -= 1
    col -= 1
    if right[row] == -1:
        right[row] = left[row] = col
    else:
        right[row] = max(right[row], col)
        left[row] = min(left[row], col)
safe = sorted(list([int(qi) - 1 for qi in input().split()]))


# print(safe)

def dist(lower, upper, row):
    if lower > upper:
        return dist(upper, lower, row)
    pos = bisect_left(safe, lower)
    options = []
    if pos < len(safe):
        if safe[pos] <= upper:
            return upper - lower
        else:
            options.append(safe[pos] - lower + safe[pos] - upper)
    pos2 = bisect_left(safe, lower) - 1
    if pos2 >= 0:
        options.append(lower - safe[pos2] + upper - safe[pos2])
    return min(options)


if left[0] == -1:
    left[0] = right[0] = 0
dleft = right[0] + (right[0] - left[0])
dright = right[0]
lastn = 0
for i in range(1, n):
    if left[i] == -1:
        continue
    ilen = right[i] - left[i]
    dleft_new = min(dleft + dist(left[lastn], right[i], i), dright + dist(right[lastn], right[i], i)) + ilen
    dright_new = min(dleft + dist(left[lastn], left[i], i), dright + dist(right[lastn], left[i], i)) + ilen
    dleft, dright = dleft_new, dright_new
    lastn = i
print(min(dleft, dright) + lastn)


from bisect import *

n, m, k, q = list(map(int, input().split()))
right = [-1] * n
left = [-1] * n
for i in range(k):
    row, col = list(map(int, input().split()))
    row -= 1
    col -= 1
    if right[row] == -1:
        right[row] = left[row] = col
    else:
        right[row] = max(right[row], col)
        left[row] = min(left[row], col)
safe = sorted(list([int(qi) - 1 for qi in input().split()]))


# print(safe)

def dist(lower, upper, row):
    posr = bisect_left(safe, lower)
    options = []
    if posr < len(safe):
        options.append(safe[posr] - lower + abs(safe[posr] - upper))
    posl = posr - 1
    if posl >= 0:
        options.append(lower - safe[posl] + abs(upper - safe[posl]))
    return min(options)


if left[0] == -1:
    left[0] = right[0] = 0
dleft = right[0] + (right[0] - left[0])
dright = right[0]
lastn = 0
for i in range(1, n):
    if left[i] == -1:
        continue
    ilen = right[i] - left[i]
    dleft_new = min(dleft + dist(left[lastn], right[i], i), dright + dist(right[lastn], right[i], i)) + ilen
    dright_new = min(dleft + dist(left[lastn], left[i], i), dright + dist(right[lastn], left[i], i)) + ilen
    dleft, dright = dleft_new, dright_new
    lastn = i
print(min(dleft, dright) + lastn)


import math
n, m, k, q = list(map(int, input().split()))
right = [-1] * n
left  = [-1] * n
for i in range(k):
    row, col = list(map(int, input().split()))
    row -= 1
    col -= 1
    if right[row] == -1:
        right[row] = left[row] = col
    else:
        right[row] = max(right[row], col)
        left[row] = min(left[row], col)
safe = sorted(list([int(qi) - 1 for qi in input().split()]))
lup = [0] * m
rup = [0] * m
j = 0
while j < safe[0]:
    lup[j] = -1
    rup[j] = safe[0]
    j += 1
lup[j] = rup[j] = safe[0]
for i in range(1, q):
    j = safe[i - 1]
    while j < safe[i]:
        lup[j] = safe[i - 1]
        rup[j] = safe[i]
        j += 1
j = safe[-1]
while j < m:
    lup[j] = safe[-1]
    rup[j] = -1
    j += 1
if left[0] == -1:
    left[0] = right[0] = 0
dleft = right[0] + (right[0] - left[0])
dright = right[0]
lastn = 0
for i in range(1, n):
    if left[i] == -1:
        continue
    left_1b = lup[left[lastn]]
    left_2b = rup[left[lastn]]
    right_1b = lup[right[lastn]]
    right_2b = rup[right[lastn]]
    ilen = right[i] - left[i]
    ll1 : int
    ll2 : int
    rl1 : int
    rl2 : int
    if left_1b != -1:
        ll1 = (left[lastn] - left_1b) + abs(right[i] - left_1b)
    else:
        ll1 = math.inf
    if left_2b != -1:
        ll2 = (left_2b - left[lastn]) + abs(right[i] - left_2b)
    else:
        ll2 = math.inf
    if right_1b != -1:
        rl1 = (right[lastn] - right_1b) + abs(right[i] - right_1b)
    else:
        rl1 = math.inf
    if right_2b != -1:
        rl2 = (right_2b - right[lastn]) + abs(right[i] - right_2b)
    else:
        rl2 = math.inf
    dleft_new = min(dleft + min(ll1, ll2), dright + min(rl1, rl2)) + ilen
    lr1 : int
    lr2 : int
    rr1: int
    rr2: int
    if left_1b != -1:
        lr1 = (left[lastn] - left_1b) + abs(left[i] - left_1b)
    else:
        lr1 = math.inf
    if left_2b != -1:
        lr2 = (left_2b - left[lastn]) + abs(left[i] - left_2b)
    else:
        lr2 = math.inf
    if right_1b != -1:
        rr1 = (right[lastn] - right_1b) + abs(left[i] - right_1b)
    else:
        rr1 = math.inf
    if right_2b != -1:
        rr2 = (right_2b - right[lastn]) + abs(left[i] - right_2b)
    else:
        rr2 = math.inf
    dright_new = min(dleft + min(lr1, lr2), dright + min(rr1, rr2)) + ilen
    dleft, dright = dleft_new, dright_new
    lastn = i
print(min(dleft, dright) + lastn)


from bisect import bisect_left
n, m, k, q = list(map(int, input().split()))
x = sorted(list(map(int, input().split())) for _ in range(k))
y = sorted(map(int, input().split()))

def rr(c0, c1, c):
    return abs(c0 - c) + abs(c1 - c)
    
def tm(c0, c1):
    t = bisect_left(y, c0)
    tt = []
    if t > 0:
        tt.append(rr(c0, c1, y[t-1]))
    if t < q:
        tt.append(rr(c0, c1, y[t]))
    return min(tt)

z = []
for r, c in x:
    if z and z[-1][0] == r:
        z[-1][2] = c
    else:
        z.append([r, c, c])
v1, v2, r0, c01, c02 = 0, 0, 1, 1, 1
for r1, c11, c12 in z:
    d = c12 - c11 + r1 - r0
    if r1 > r0:
        d11 = tm(c01, c11)
        d12 = tm(c01, c12)
        d21 = tm(c02, c11)
        d22 = tm(c02, c12)
        v2, v1 = d + min(v1 + d11, v2 + d21), d + min(v1 + d12, v2 + d22)
    else:
        v1, v2 = d + c12 - c02, d + c11 - c01
    r0, c01, c02 = r1, c11, c12
print(min(v1, v2))


def nearest(point):
    l = 0
    r = q
    while r - l > 1:
        mid = int((r + l) / 2)
        if safe[mid] <= point:
            l = mid
        else:
            r = mid
    if safe[l] > point:
        return [safe[l]]
    elif l + 1 == q:
        return [safe[l]]
    else:
        return [safe[l], safe[l + 1]]


def way(come, row, side=True):
    between = abs(right[row] - left[row])
    if side:
        return abs(come - left[row]) + between
    else:
        return abs(come - right[row]) + between


n, m, k, q = [int(x) for x in input().split()]
right = [-1] * n
left = [-1] * n

for i in range(k):
    a, b = [int(x) - 1 for x in input().split()]
    if right[a] == -1:
        right[a] = left[a] = b
    else:
        right[a] = max(right[a], b)
        left[a] = min(left[a], b)
safe = [int(x) - 1 for x in input().split()]
safe.sort()
left[0] = right[0]
if right[0] == -1:
    L = R = min(nearest(0))
    right[0] = left[0] = L
else:
    L = R = right[0]
while right[n - 1] == -1:
    n -= 1
last = 0
for i in range(1, n):
    # print(last)
    # print(L, R)
    L += 1
    R += 1
    if right[i] == -1:
        continue
    left_way = 100000000000
    right_way = 100000000000
    lcolumns = nearest(left[last])
    rcolumns = nearest(right[last])
    for c in lcolumns:
        left_way = min(left_way, L + way(c, i, False) + abs(c - left[last]))
        right_way = min(right_way, L + way(c, i, True) + abs(c - left[last]))
    for c in rcolumns:
        left_way = min(left_way, R + way(c, i, False) + abs(c - right[last]))
        right_way = min(right_way, R + way(c, i, True) + abs(c - right[last]))
    # print(left_way, right_way)
    L = left_way
    R = right_way
    last = i
print(min(L, R))#+ (n - 1))

import sys
n, m, k, q = [int(i) for i in sys.stdin.readline().split()]
indata = sys.stdin.readlines()
data = []
inf = 1<<50


for i in range(k):
    data.append(tuple([int(f) for f in indata[i].split()]))

data.sort()
chutes = [int(i) for i in indata[-1].split()]
chutes.sort()
nearch = [(0,0)]*(m+1)
for i in range(1, chutes[0]+1):
    nearch[i] = (chutes[0], chutes[0])
for i in range(q-1):
    a = chutes[i] 
    b = chutes[i+1]
    for j in range(a+1, b):
        nearch[j] = (a,b)
    nearch[b] = (b,b)
for i in range(chutes[-1], m+1):
    nearch[i] = (chutes[-1],chutes[-1])

lastr = -1
rows = []
rowdata = {}
for d in data:
    if d[0] != lastr:
        lastr = d[0]
        rows.append(d[0])
        rowdata[d[0]] = []
    rowdata[d[0]].append(d[1])


dp = [ [ (1, 0), (1, 0) ] ]
start = 0
if rows[0] == 1:
    #1+' '
    #dp[0] = [   (rowdata[1][-1], rowdata[1][-1] - 1 ) ,    (rowdata[1][0], 2 * rowdata[1][-1] - rowdata[1][0] - 1) ]
    dp[0] = [   (rowdata[1][-1], rowdata[1][-1] - 1 ) ,    (1, inf) ]
    start = 1

lnr = len(rows)
for i in range(start, lnr):
    row = rowdata[rows[i]]
    # ldp = dp[-1]
    LR = (0,inf)
    for f in range(4):
        ldp = dp[-1][f//2]
        am = ldp[1]
        d = nearch[ldp[0]][f%2]
        am += abs(ldp[0] - d)
        am += abs(d - row[0])
        am += row[-1] - row[0]

        if am < LR[1]:
            LR = (row[-1], am)
    
    RL = (0,inf)
    for f in range(4):
        ldp = dp[-1][f//2]
        am = ldp[1]
        d = nearch[ldp[0]][f%2]
        am += abs(ldp[0] - d)
        am += abs(d - row[-1])
        am += row[-1] - row[0]

        if am < RL[1]:
            RL = (row[0], am)
    dp.append([LR, RL])



# print(rows)
# print(rowdata) 
# print(dp)

print(min(dp[-1][0][1], dp[-1][1][1]) + rows[-1] - 1)





from sys import stdin
from bisect import bisect_left
input=stdin.readline
n,m,k,q=list(map(int,input().split(' ')))
x=sorted(list(map(int,input().split(' ')))for i in range(k))
y=sorted(list(map(int,input().split(' '))))
def rr(c0,c1,c2):
    return abs(c2-c0)+abs(c1-c2)

def tm(c0,c1):
    t=bisect_left(y,c0)
    tt=[]
    if (t>0):
        tt.append(rr(c0,c1,y[t-1]))
    if (t<q):
        tt.append(rr(c0,c1,y[t]))
    return min(tt)

    





# thực hiện tìm xem trong một hàng, kho báu nằm từ khoảng nào đến khoảng nào.
z=[]
for r,c in x:
    if z and z[-1][0]==r:
        z[-1][2]=c
    else:
        z.append([r,c,c])
v1,v2,r0,c01,c02=0,0,1,1,1
for r1,c11,c12 in z:
    d=c12-c11+r1-r0
    # bình thường
    if(r1>r0):
        d01=tm(c01,c11)
        d02=tm(c01,c12)
        d11=tm(c02,c11)
        d12=tm(c02,c12)
        v2,v1=d+min(v1+d01,v2+d11),d +min(v1+d02,v2+d12)

    #nếu có kho báu ở hàng 1
    else:
        v1,v2=d+c12-c02,d+c11-c01
    c01,c02,r0=c11,c12,r1
ans=min(v1,v2)
print(ans)