Description

Penguinland 是一条无限的数轴，上面有 $n$ 只怪物。第 $i$ 只怪物最初位于数轴上的位置 $a[i]$，其生命值为 $h[i]$。保证没有两只怪物具有相同的初始位置。

今天，企鹅 Brian 想要打败所有的怪物！为了打败它们，Brian 在某些位置埋下了 $k$ 颗地雷。第 $j$ 颗地雷位于位置 $x[j]$。引爆一颗地雷会立即摧毁所有站在该位置的怪物，并且每颗地雷可以被引爆任意次数。然而，每次引爆的代价是 $1$ 美元。保证没有两颗地雷被埋在相同的位置。

除了引爆地雷，Brian 还可以执行两种操作：

• 将一只怪物向左或向右移动 $1$ 个单位距离。
• 增加或减少一只怪物的生命值 $1$。

每次操作的代价是 $1$ 美元。

如果一只怪物的生命值降至 $0$ 或者它被地雷摧毁，则认为该怪物被打败。请帮助 Brian 找出打败所有怪物所需的最小代价（以美元计）。

Input Format

你的程序必须从标准输入读取数据。

输入的第一行包含两个以空格分隔的整数 $n$ 和 $k$。

接下来的 $n$ 行，每行包含两个以空格分隔的整数。第 $i$ 行包含 $a[i]$ 和 $h[i]$。

最后一行包含 $k$ 个以空格分隔的整数 $x[1], x[2], \ldots, x[k]$。

Output Format

你的程序必须将结果打印到标准输出。

输出一个单独的整数，即打败所有怪物所需的最小代价（以美元计）。

输出应仅包含一个整数，不要打印任何额外的文本，例如 “输入一个数字” 或 “答案是”。

3 1
2 2
4 5
5 4
5

4

5 2
7 7
6 3
10 4
4 4
9 1
7 10

7

10 5
19 10
5 3
1 2
3 6
17 2
20 3
8 2
12 3
14 2
15 1
40 13 37 14 6

23

Hint

子任务

对于所有测试用例，输入将满足以下约束条件：

• $1 \leq n, k \leq 200\,000$
• 对于所有 $1 \leq i \leq n$，有 $1 \leq a[i], h[i] \leq 10^9$
• 对于所有 $1 \leq i \leq k$，有 $1 \leq x[i] \leq 10^9$
• 对于所有 $i \neq j$，有 $a[i] \neq a[j]$
• 对于所有 $i \neq j$，有 $x[i] \neq x[j]$

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 1 解释

此样例适用于子任务 $1, 3, 4, 6$。

有 $n = 3$ 只怪物和 $k = 1$ 颗地雷。Brian 可以：

• 将怪物 $1$ 的生命值减少至 $0$，花费 $2$ 美元。
• 将怪物 $2$ 向右移动 $1$ 个单位（位置从 $4$ 变为 $5$），花费 $1$ 美元。
• 引爆位置 $5$ 处的地雷，击败怪物 $2$ 和怪物 $3$，花费 $1$ 美元。

总花费为 $2 + 1 + 1 = 4$ 美元。

样例 2 解释

此样例适用于子任务 $2, 3, 4, 6$。

有 $n = 5$ 只怪物和 $k = 2$ 颗地雷。Brian 可以：

• 将怪物 $5$ 的生命值减少至 $0$，花费 $1$ 美元。
• 引爆地雷 $2$，击败怪物 $3$，花费 $1$ 美元。
• 将怪物 $2$ 向右移动 $1$ 个单位（位置从 $6$ 变为 $7$），花费 $1$ 美元。
• 将怪物 $4$ 向右移动 $3$ 个单位（位置从 $4$ 变为 $7$），花费 $3$ 美元。
• 引爆地雷 $1$，击败怪物 $1, 2, 4$，花费 $1$ 美元。

总花费为 $1 + 1 + 1 + 3 + 1 = 7$ 美元。

样例 3 解释

此样例适用于子任务 $3, 4, 6$。