[AdditionalFile5267.zip](file://AdditionalFile5267.zip?type=additional_file)

#5267. 「NOISG 2025 Final」Monsters

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2025 Final T1. Monsters

在企鹅大陆上，有一条无限长的数轴，上面分布着 $n$ 只怪兽。第 $i$ 只怪兽初始位于数轴上的位置 $a[i]$，其生命值为 $h[i]$。保证任意两只怪兽的初始位置均不相同。

今天，企鹅布莱恩希望击败所有怪兽！为此，布莱恩在数轴上放置了 $k$ 个地雷。第 $j$ 个地雷位于位置 $x[j]$。引爆一个地雷会立即消灭位于该位置的所有怪兽，且每个地雷可以被多次引爆，但每次引爆需花费 1 元的费用。保证任意两个地雷的位置均不相同。

除了引爆地雷，布莱恩还可以执行以下两种操作：

• 将一只怪兽沿数轴向左或向右移动 $1$ 个单位。
• 将一只怪兽的生命值增加或减少 $1$。

每次操作需花费 $1$ 元的费用。一只怪兽的生命值降为 $0$ 或被地雷消灭时，即视为被击败。请帮助布莱恩计算击败所有怪兽所需的最小费用（以元为单位）。

输入格式

程序需从标准输入读取数据。

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

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

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

输出格式

程序需向标准输出输出结果。

输出一个整数，表示击败所有怪兽所需的最小费用（以元为单位）。

输出仅包含一个整数，不应包含任何额外文本，如 Enter a number 或 The answer is。

样例 1

输入

3 1
2 2
4 5
5 4
5

输出

4

有 $n=3$ 只怪兽和 $k=1$ 个地雷。布莱恩可以：

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

总费用为 $2+1+1=4$ 元。

这个样例满足子任务 $1,3,4,6$ 的限制。

样例 2

输入

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

输出

7

有 $n=5$ 只怪兽和 $k=2$ 个地雷。布莱恩可以：

• 将怪兽 $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$ 元。

这个样例满足子任务 $2,3,4,6$ 的限制。

样例 3

输入

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

这个样例满足子任务 $3,4,6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$14$	$k=1$
$2$	$6$	$k=2$
$3$	$10$	$n, k \leq 18$
$4$	$30$	$n, k \leq 3000$
$5$	$29$	$h[i]=10^{9}$
$6$	$11$	无附加限制