CF1201D.Treasure Hunting

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.

你位于一个可以表示为 $n \times m$ 表格的岛屿上。行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。岛上共有 $k$ 个宝藏，其中第 $i$ 个宝藏位于位置 $(r_i, c_i)$。

初始时，你站在岛屿的左下角，即位置 $(1, 1)$。在任意时刻，若你所在格子中有一个宝藏，你可立即拾取它，且不额外消耗时间。每次移动，你可以向上（从 $(r, c)$ 移动到 $(r+1, c)$）、向左（从 $(r, c)$ 移动到 $(r, c-1)$）或向右（从 $(r, c)$ 移动到 $(r, c+1)$）。由于存在陷阱，你不能向下移动。

然而，向上移动也存在风险：你仅当处于安全列中时才能向上移动。共有 $q$ 个安全列：$b_1, b_2, \ldots, b_q$。你希望以最快速度收集全部宝藏。请计算收集所有宝藏所需的最少移动次数。

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.

第一行包含四个整数 $n$、$m$、$k$ 和 $q$（$2 \le n, \, m, \, k, \, q \le 2 \cdot 10^5$，且 $q \le m$）——分别表示岛屿的行数、列数、宝藏数量以及安全列的数量。

接下来的 $k$ 行中，每行包含两个整数 $r_i$、$c_i$（$1 \le r_i \le n$，$1 \le c_i \le m$）——表示第 $i$ 个宝藏所在单元格的坐标。所有宝藏均位于互不相同的单元格中。

最后一行包含 $q$ 个互不相同的整数 $b_1, b_2, \ldots, b_q$（$1 \le b_i \le m$）——表示安全列的列号。

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

输出收集所有宝藏所需的最少移动次数。

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.

在第一个例子中，你应该使用第二列向上移动，在每一行中收集第一列的宝藏。

在第二个例子中，最优策略是使用第一列向上移动。

在第三个例子中，最优策略是：先收集单元格 $(1;6)$ 处的宝藏，然后在第 $6$ 列向上移动至第 $2$ 行，再收集单元格 $(2;2)$ 处的宝藏，接着在第 $1$ 列向上移动至最顶行，并最后收集单元格 $(3;4)$ 处的宝藏。总共需要 $15$ 步。