P15497 [ICPC 2025 APC] Hold the Star

你正在玩一个电脑游戏，游戏中有 $n$ 个房间，$m$ 个角色和一颗星星。房间从左到右排列，依次编号为 $1$ 到 $n$。角色编号为 $1$ 到 $m$。在任何时刻，每个角色都在某个房间内，而星星要么在某个房间内，要么被某个角色持有。游戏的目标是让星星被角色 $m$ 持有。 你可以通过执行若干动作来玩这个游戏。每个动作消耗一定数量的星币（游戏中的货币单位），可能为零。在每个动作中，你选择一个角色 $x$（设该角色当前所在的房间为 $y$），并命令该角色执行以下操作之一： - 移动到相邻的房间（$y-1$ 或 $y+1$），如果该房间存在。如果角色 $x$ 正持有星星，则角色继续持有星星。该动作消耗 $s_x$ 星币。$s_1, s_2, \ldots, s_m$ 的值已给定。 - 拾起星星并持有它，前提是星星当前在房间 $y$ 且未被任何角色持有。该动作消耗 $0$ 星币。 - 放下星星并释放它，前提是星星当前被角色 $x$ 持有。星星随后落到房间 $y$。该动作消耗 $0$ 星币。 游戏包含 $q$ 个关卡，编号为 $1$ 到 $q$。在所有关卡中，每个角色 $i$ 初始位于房间 $r_i$，且角色 $m$ 必须持有星星才能通关。关卡之间的唯一区别在于，在每个关卡 $j$ 中，星星初始位于房间 $l_j$。 对于每个关卡，你需要计算通关所需花费的最小总星币。注意，你不必最小化动作次数。

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1\le n\le 10^9$；$1\le m\le 100\,000$；$1\le q\le 100\,000$）。接下来的 $m$ 行中的第 $i$ 行包含两个整数 $r_i$ 和 $s_i$（$1\le r_i\le n$；$1\le s_i\le 10^9$）。接下来的 $q$ 行中的第 $j$ 行包含一个整数 $l_j$（$1\le l_j\le n$）。

按顺序对于每个关卡，输出通关所需花费的最小总星币。

**样例输入/输出 #1 的解释** 你可以通过以下动作消耗 $5$ 星币通关第一关： 1. 角色 5 从房间 2 移动到房间 1。该动作消耗 $5$ 星币。 2. 角色 5 拾起星星。 你可以通过以下动作消耗 $0$ 星币通关第二关： 1. 角色 5 拾起星星。 你可以通过以下动作消耗 $8$ 星币通关第三关： 1. 角色 4 拾起星星。 2. 角色 4 从房间 5 移动到房间 4。该动作消耗 $3$ 星币。 3. 角色 4 从房间 4 移动到房间 3。该动作消耗 $3$ 星币。 4. 角色 4 放下星星。 5. 角色 2 拾起星星。 6. 角色 2 从房间 3 移动到房间 2。该动作消耗 $2$ 星币。 7. 角色 2 放下星星。 8. 角色 5 拾起星星。 你可以通过以下动作消耗 $14$ 星币通关第四关： 1. 角色 2 从房间 3 移动到房间 4，然后到房间 5，然后到房间 6。这些动作总共消耗 $3 \times 2 = 6$ 星币。 2. 角色 2 拾起星星。 3. 角色 2 从房间 6 移动到房间 5，然后到房间 4，然后到房间 3，然后到房间 2。这些动作总共消耗 $4 \times 2 = 8$ 星币。 4. 角色 2 放下星星。 5. 角色 5 拾起星星。 翻译由 DeepSeek 完成