你所在的岛屿可以表示为 $$$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$$$。你想尽快收集所有的宝藏。计算收集所有宝藏所需的最少移动次数。
输入
第一行包含整数 $$$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$$$) — 有宝藏的单元格的坐标。所有宝藏都位于不同的牢房中。
最后一行包含 $$$q$$$ 不同的整数 $$$b_1, b_2, \ldots, b_q$$$ ($$$1 \le b_i \le m$$$) — 安全列的索引。
输出
打印收集所有宝藏所需的最少移动次数。
示例
输入 #1
3 3 3 2 1 1 2 1 3 1 2 3
输出 #1
6
输入 #2
3 5 3 2 1 2 2 3 3 1 1 5
输出 #2
8
输入 #3
3 6 3 2 1 6 2 2 3 4 1 6
输出 #3
15
注意
在第一个示例中,您应该使用第二列向上,从第一列收集每行的宝藏。
在第二个示例中,最好使用第一列向上。
在第三个示例中,最佳做法是在单元格 $$$(1;6)$$$ 处收集宝藏,向上至 $$$6$$$ 列的行 $$$2$$$,然后在单元格 $$$(2;2)$$$ 处收集宝藏,向上至 $$$1$$$ 列的顶行,并在单元格 $$$(3;4)$$$ 处收集最后一个宝藏。总共移动了 $$$15$$$。