Treasure Hunting

题目描述 有一个$n*m$的矩阵，行的标号从$1$到$n$，列的标号从$1$到$m$，矩阵中共有$k$个宝藏，第$i$个宝藏的位置为$(r_i,c_i)$。有$q$个安全的列，第$i$个安全的列的编号是$b_i$。 最初你站在矩阵的左下角（也就是$(1,1)$的位置），并且可以向左走（从$(r,c)$到$(r,c-1)$）和向右走（从$(r,c)$到$(r,c+1)$）。同时，你也可是向上走（从$(r,c)$到$(r+1,c)$），但是你必须在安全的列上。由于某些玄学原因，你不可以向下走。 你的任务是收集所有的宝藏，但是你的时间已经不多了，所以你必须走最快的路径。现在你要使用你的人脑大法来计算出最快的路径需要多少时间（经过有宝藏的格子时收集宝藏不消耗时间，只有移动消耗时间）。 输入格式 第一行为四个整数$n,m,k,q(2≤n,m,k,q≤2*10^5,q≤m)$——行数，列数，宝藏个数，安全的列的个数。 接下来$k$行每行两个整数$r_i,c_i(1≤r_i≤n,1≤c_i≤m)$——宝藏的位置。 最后一行为$q$个整数$b_1,b_2,...,b_q$——安全的列的编号。 输出格式 一个整数，最快的路径需要的时间。

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.

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.

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

3 3 3 2
1 1
2 1
3 1
2 3

6

3 5 3 2
1 2
2 3
3 1
1 5

8

3 6 3 2
1 6
2 2
3 4
1 6

15

In the first example you should use the second column to go up, collecting in each row treasures from the first column. In the second example, it is optimal to use the first column to go up. 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.