P16515 [GKS 2015 #D] gBalloon
题目描述
G 科技公司部署了许多气球。有时，需要将它们收集到位于水平位置 $0$ 的公司塔楼处进行维护。每个气球当前位于水平位置 $P_i$ 和高度 $H_i$。
G 公司的工程师可以通过发送无线电信号让气球丢弃压舱物或放出空气，从而使气球上下移动。但他们无法水平移动气球，只能依靠现有的风来实现水平移动。
气球可能处于 $M$ 个不同的高度。不同高度的风可能以不同的方向和速度吹动。具体来说，在高度 $j$ 处，风速为 $V_j$，正速度表示风从左向右吹，负速度表示风从右向左吹。位于某个高度、风速为 $V$ 的气球，在位置 $P$ 处，经过一个时间单位后将到达位置 $P+V$，经过两个时间单位后到达 $P+2V$，依此类推。如果气球触碰到塔楼，它会立即被收集。
将一个气球在两个不同高度之间移动需要消耗 $| H_{\text{原高度}} - H_{\text{新高度}} |$ 点的能量。（这种转移不消耗时间。）你拥有 $Q$ 点能量可供使用，不过不必全部用完。如果你以最优方式消耗能量，收集所有气球所需的最短时间是多少？
输入格式
输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行有三个整数 $N$、$M$ 和 $Q$，分别表示气球的数量、高度层级的数量以及可用的能量值。
第二行包含 $M$ 个整数；该行中的第 $j$ 个值（从 $0$ 开始计数）是高度 $j$ 处的风速。
接下来是 $N$ 行。其中第 $i$ 行包含两个整数 $P_i$ 和 $H_i$，表示第 $i$ 个气球的位置和高度。
输出格式
对于每个测试用例，输出一行形如 `Case #x: y` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是收集所有气球所需的最少时间单位数。如果使用给定的能量无法收集所有气球，则输出 `IMPOSSIBLE`。
说明/提示
下面是一个例子：
:::align{center}
:::
在样例用例中，天空中有 $2$ 个气球，你有 $1$ 个能量点可用。最佳方案是立即花费 $1$ 个能量点，将位于位置 $3$、高度 $3$ 的气球下降到高度 $2$。完成后，两个气球都需要 $2$ 个时间单位才能到达塔楼。
### 限制
**小数据集（测试集 1 - 可见）**
$1 \le T \le 100$。
$1 \le N \le 10$。
$1 \le M \le 10$。
$-10 \le V_j \le 10$。
$1 \le Q \le 10$。
$0 \le H_i < M$。
$-10 \le P_i \le 10$。
**大数据集（测试集 2 - 隐藏）**
$1 \le T \le 25$。
$1 \le N \le 100$。
$1 \le M \le 1000$。
$-100 \le V_j \le 100$。
$1 \le Q \le 10000$。
$0 \le H_i < M$。
$-10000 \le P_i \le 10000$。
翻译由 DeepSeek V4 Pro 完成