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]

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Sorting

Implementation

Greedy algorithms


Solutions:
import bisect
(n, m, k, q) = map(int, input().split())
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)
total = highest - 1
total += min(old_a, old_b)
print(total)


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()]))

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)


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))


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)


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
left = [1000000] * 200005
right = [0] * 200005
(n, m, k, q) = rrd()
lst = 0
while k:
	(x, y) = rrd()
	left[x] = min(y, left[x])
	right[x] = max(right[x], y)
	lst = max(lst, x)
	k -= 1
qt = list(rrd())
qt.sort()
from bisect import *
pre = [1] * 4
dpp = [0] * 4
dpn = [0] * 4
for i in range(1, lst):
	now = [0] * 4
	dpn = [500000000000] * 4
	if not right[i]:
		dpp = list(map(lambda x: x + 1, dpp))
		if i == 1:
			pre = [qt[0]] * 4
			dpp = [qt[0]] * 4
		continue
	l = bisect_left(qt, left[i])
	r = bisect_left(qt, right[i])
	if l < q and qt[l] == left[i]:
		now[0] = qt[l]
		now[1] = qt[l]
	else:
		now[0] = qt[l - 1] if l else 0
		now[1] = qt[l] if l < q else 0
	if r < q and qt[r] == right[i]:
		now[2] = qt[r]
		now[3] = qt[r]
	else:
		now[2] = qt[r - 1] if r else 0
		now[3] = qt[r] if r < q else 0
	for j in range(4):
		if not now[j]:
			continue
		for k in range(4):
			if not pre[k]:
				continue
			l = min(abs(right[i] - pre[k]) + abs(left[i] - now[j]), abs(right[i] - now[j]) + abs(left[i] - pre[k])) + 1
			dpn[j] = min(dpn[j], dpp[k] + right[i] - left[i] + l)
	pre = now[:]
	dpp = dpn[:]
ans = min((dpp[i] + right[lst] - left[lst] + min(abs(pre[i] - left[lst]), abs(pre[i] - right[lst])) for i in range(4)))
print(ans)


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()
b = list(map(int, sys.stdin.readline().strip().split()))
b.sort()
for i in range(0, q):
	b[i] = b[i] - 1
L = [b[0]] * m
R = [b[-1]] * m
R1 = [10 ** 6] * n
R2 = [-1] * n
n1 = 0
n2 = 0
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]))


(n, m, k, q) = map(int, input().split())
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()))

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)
	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):
	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])
	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
answ = l + tr_min[last_valid]
print(answ)


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)


import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
(n, m, k, q) = map(int, input().split())
treasure = [[] for i in range(n)]
for _ in range(k):
	(x, y) = map(int, input().split())
	treasure[x - 1].append(y - 1)
safe = list(map(int, input().split()))
for i in range(q):
	safe[i] -= 1
safe.sort()
left = 0
right = 1
real = [[-1, -1] for i in range(n)]
for i in range(n):
	if treasure[i]:
		real[i][left] = min(treasure[i])
		real[i][right] = max(treasure[i])
dp = [[0, 0] for i in range(n)]
if real[0][right] != -1:
	dp[0][left] = real[0][right]
	dp[0][right] = real[0][right]
	real[0][left] = real[0][right]
else:
	dp[0][left] = 0
	dp[0][right] = 0
	real[0][left] = 0
	real[0][right] = 0

def go(a, b):
	if a < b:
		(a, b) = (b, a)
	bl = bisect_left(safe, b)
	ar = bisect_right(safe, a)
	if ar > bl:
		return a - b + 1
	else:
		ret = int(1000000000.0)
		al = bisect_left(safe, a)
		br = bisect_right(safe, b)
		if al != q:
			ret = min((safe[al] - a) * 2 + 1 + a - b, ret)
		if br != 0:
			ret = min((b - safe[br - 1]) * 2 + 1 + a - b, ret)
		return ret
cnt = 0
pre = 0
maxx = 0
for i in range(1, n):
	if real[i][left] == -1:
		cnt += 1
	else:
		dp[i][left] = min(dp[pre][right] + go(real[pre][right], real[i][right]), dp[pre][left] + go(real[pre][left], real[i][right])) + cnt + real[i][right] - real[i][left]
		dp[i][right] = min(dp[pre][right] + go(real[pre][right], real[i][left]), dp[pre][left] + go(real[pre][left], real[i][left])) + cnt + real[i][right] - real[i][left]
		cnt = 0
		pre = i
print(min(dp[pre]))


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):
	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]))
	L = left_way
	R = right_way
	last = i
print(min(L, R))


import sys
import math
from bisect import *
(n, m, k, q) = map(int, input().split())
L = [math.inf] * n
R = [0] * n
H = 0
input = sys.stdin.readlines()
for _ in range(k):
	(y, x) = map(int, input[_].split())
	H = max(H, y)
	L[y - 1] = min(L[y - 1], x)
	R[y - 1] = max(R[y - 1], x)
a = sorted(map(int, input[k].split()))
br = None

def find_br(i):
	global br
	find = lambda x: bisect_right(a, x, hi=len(a) - 1)
	br = [0, find(L[i]), 0, find(R[i])]
	br[0] = max(0, br[1] - 1)
	br[2] = max(0, br[3] - 1)
	br = [a[i] for i in br]
if R[0]:
	dp = [0] * 4
	br = [1] * 4
else:
	dp = [(H > 1) * a[0] - 1] * 4
	br = [a[0]] * 4
for i in range(n):
	if R[i]:
		dpp = dp
		dp = [math.inf] * 4
		brp = br
		find_br(i)
		for j in range(4):
			for k in range(4):
				dp[j] = min(dp[j], dpp[k] + (R[i] - L[i]) + abs(brp[k] - L[i]) + (i + 1 < H) * abs(br[j] - R[i]))
				dp[j] = min(dp[j], dpp[k] + (R[i] - L[i]) + abs(brp[k] - R[i]) + (i + 1 < H) * abs(br[j] - L[i]))
print(min(dp) + H - 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)
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:
		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))
	else:
		(v1, v2) = (d + c12 - c02, d + c11 - c01)
	(c01, c02, r0) = (c11, c12, r1)
ans = min(v1, v2)
print(ans)


[n, m, k, q] = [int(w) for w in input().split()]
trs = [[int(w) - 1 for w in input().split()] for _ in range(k)]
b = [int(w) - 1 for w in input().split()]
b.sort()
b.append(b[-1])
br = bl = 0
er = []
el = []
for i in range(m):
	if br < q and i > b[br]:
		bl = br
		br += 1
	el.append(b[bl])
	er.append(b[br])
for x in b:
	el[x] = er[x] = x
g = [None for _ in range(n)]
dy = 0
for (r, c) in trs:
	if g[r] is None:
		g[r] = (c, c)
	else:
		(a, b) = g[r]
		if c < a:
			g[r] = (c, b)
		elif c > b:
			g[r] = (a, c)
	if r > dy:
		dy = r
if g[0] is not None:
	(_, xr) = g[0]
else:
	xr = 0
dxl = dxr = xl = xr
for i in range(1, n):
	if g[i] is None:
		continue
	(gl, gr) = g[i]
	d = gr - gl
	(dxr, dxl) = (d + min(dxl + abs(gl - el[xl]) + abs(xl - el[xl]), dxl + abs(gl - er[xl]) + abs(xl - er[xl]), dxr + abs(gl - el[xr]) + abs(xr - el[xr]), dxr + abs(gl - er[xr]) + abs(xr - er[xr])), d + min(dxl + abs(gr - el[xl]) + abs(xl - el[xl]), dxl + abs(gr - er[xl]) + abs(xl - er[xl]), dxr + abs(gr - el[xr]) + abs(xr - el[xr]), dxr + abs(gr - er[xr]) + abs(xr - er[xr])))
	(xl, xr) = (gl, gr)
print(min(dxl, dxr) + dy)


import os
import sys
import bisect as bi
from io import BytesIO, IOBase

def main():
	I = lambda : list(map(int, input().split()))
	(n, m, k, q) = map(int, input().split())
	x = sorted((list(map(int, input().split())) for _ in range(k)))
	y = sorted(map(int, input().split()))

	def rr(a, b, c):
		return abs(a - c) + abs(b - c)

	def tm(a, b):
		ind = bi.bisect_left(y, a)
		temp = []
		if ind > 0:
			temp.append(rr(a, b, y[ind - 1]))
		if ind < q:
			temp.append(rr(a, b, y[ind]))
		return min(temp)
	te = []
	for (r, c) in x:
		if te and te[-1][0] == r:
			te[-1][2] = c
		else:
			te.append([r, c, c])
	(v1, v2, r0, c01, c02) = (0, 0, 1, 1, 1)
	for (r1, c11, c12) in te:
		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))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(n, m, k, q) = 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}
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
LAST = 1 << 50
if TRLIST[n] == []:
	print(min(START.values()) + n - 1)
	sys.exit()
MIN = min(TRLIST[n])
MAX = max(TRLIST[n])
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)


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 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:
	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]]
	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(min(dp[-1][0][1], dp[-1][1][1]) + rows[-1] - 1)