P12015 [NOISG 2025 Finals] 怪物

Penguinland 是一条无限的数轴，上面有 $n$ 只怪物。第 $i$ 只怪物最初位于数轴上的位置 $a[i]$，其生命值为 $h[i]$。保证没有两只怪物具有相同的初始位置。 今天，企鹅 Brian 想要打败所有的怪物！为了打败它们，Brian 在某些位置埋下了 $k$ 颗地雷。第 $j$ 颗地雷位于位置 $x[j]$。引爆一颗地雷会**立即摧毁所有**站在该位置的怪物，并且每颗地雷可以被引爆任意次数。然而，每次引爆的代价是 $1$ 美元。保证没有两颗地雷被埋在相同的位置。 除了引爆地雷，Brian 还可以执行两种操作： - 将一只怪物向左或向右移动 $1$ 个单位距离。 - 增加或减少一只怪物的生命值 $1$。 每次操作的代价是 $1$ 美元。 如果一只怪物的生命值降至 $0$ 或者它被地雷摧毁，则认为该怪物被打败。请帮助 Brian 找出打败所有怪物所需的最小代价（以美元计）。

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $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]$ 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $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$ | 无 | ### 样例 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$。