题目描述

Ada 在一个由 $N$ 条水平街道和 $N$ 条垂直街道组成的城市中配送披萨，这些街道分别从北到南、从西到东编号为 $1$ 到 $N$。网格的左上角交叉点为 $(1, 1)$。

今天，Ada 需要为 $P$ 位顾客配送 $P$ 份披萨，每位顾客各一份。每位顾客住在不同的街道交叉点；第 $k$ 位顾客住在交叉点 $(X_k, Y_k)$，并在披萨送达后支付 Ada $C_k$ 枚硬币。

Ada 从披萨餐厅 $(A_r, A_c)$ 出发，初始有 $0$ 枚硬币，并携带 $P$ 份披萨。她的目标是在 $M$ 分钟内将所有披萨送达。她可以自由选择城市中的任意路径，只要能在 $M$ 分钟内将所有披萨分别送到对应的顾客手中，她可以在任何地点结束。在两个相邻的街道交叉点之间行走需要 $1$ 分钟，而在顾客位置放下披萨不消耗额外时间。需要注意以下额外规则和约束：

• Ada 不得离开网格。
• 没有顾客与 Ada 的出发点位于同一交叉点。
• Ada 可以在任意时刻选择停留在当前位置不移动。
• Ada 到达顾客位置时，也可以选择不送达披萨。

形式化地说，如果 Ada 当前位于交叉点 $(i, j)$（$i$ 为从上往下的行号，$j$ 为从左往右的列号），她可以选择执行以下任意操作（只要不离开网格）：

• 向北移动，到达交叉点 $(i - 1, j)$。
• 向东移动，到达交叉点 $(i, j + 1)$。
• 向西移动，到达交叉点 $(i, j - 1)$。
• 向南移动，到达交叉点 $(i + 1, j)$。
• 停留在交叉点 $(i, j)$。

:::align{center} :::

城市设有独特的街道使用收费系统。使用每条街道都需支付通行费，通行费取决于 Ada 当前持有的硬币数量以及她移动的方向。每个基本方向（北、东、西、南）分别定义了通行费函数 $F_d$，该函数返回 Ada 沿方向 $d$ 移动后所拥有的硬币数量，定义如下：

$$F_d = c \ \mathrm{OP}_d \ K_d$$

其中 $c$ 是 Ada 当前持有的硬币数，$\mathrm{OP}_d$ 是一个运算符，$K_d$ 是一个固定的正整数。允许的运算符有：

• $+$（加法）
• $-$（减法）
• $\times$（乘法）
• $/$（整数除法）

例如，我们可以有 $F_{\text{北}} = c + 3$，$F_{\text{东}} = c \times 4$，$F_{\text{西}} = c - 4$，$F_{\text{南}} = c / 2$。

这意味着，如果 Ada 向北移动一个街区，她将获得 $3$ 枚硬币；如果向东移动，她的硬币将翻四倍；如果向西移动，她将失去 $4$ 枚硬币；如果向南移动，她的硬币将减半。

所有除法均为整数除法，使用向下取整函数。例如，

$$-\frac{1}{4} = \left\lfloor -\frac{1}{4} \right\rfloor = -1.$$

注意，Ada 允许持有负数枚硬币。注意，通行费实际上可能反而给 Ada 增加硬币。

请判断 Ada 能否在 $M$ 分钟内送达所有 $P$ 份披萨，如果能，则求出 $M$ 分钟后 Ada 能拥有的最大硬币数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含 $N$、$P$、$M$、$A_r$、$A_c$，分别表示网格大小、需要配送的披萨数量、要求完成配送的分钟数，以及 Ada 的起始交叉点坐标。

接下来的 $4$ 行分别表示北、东、西、南方向的通行费函数。每行包含运算符 $\mathrm{OP}_d$（取值为 $+$、$-$、$*$、$/$ 之一）和正整数 $K_d$。

接下来的 $P$ 行描述每位顾客。每行包含三个整数 $X_k$、$Y_k$、$C_k$，分别表示第 $k$ 位顾客所在的行号（从上往下）、列号（从左往右），以及配送完成后支付的硬币数。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 IMPOSSIBLE（如果无法在 $M$ 分钟内送达所有披萨），否则输出 $M$ 分钟后 Ada 能拥有的最大硬币数（可能为负数）。

2
3 0 1 1 2
+ 1
- 2
+ 3
/ 4
3 0 1 2 3
- 2
- 2
- 2
- 2

Case #1: 3
Case #2: 0

3
3 1 3 1 3
+ 4
- 2
* 1
/ 4
1 2 4
2 2 1 1 2
+ 2
+ 3
* 2
* 1
1 1 4
2 2 1
3 1 2 1 3
+ 1
* 1
- 3
/ 4
2 2 2

Case #1: 8
Case #2: IMPOSSIBLE
Case #3: 1

提示

在样例 #1 中，Ada 无需配送任何披萨。Ada 位于交叉点 $(1, 2)$。在 $1$ 分钟内，她可以选择向西移动到 $(1, 1)$，这样在 $(1, 2)$ 处使用向西的通行费函数 $F_{\text{西}} = c + 3$，得到 $3$ 枚硬币。因此，Ada 在 $1$ 分钟后最多能拥有 $3$ 枚硬币。

在样例 #2 中，Ada 无需配送任何披萨。Ada 位于交叉点 $(2, 3)$。所有方向的通行费函数类似：$F_d = c - 2$。如果她朝任何方向移动，最终会得到 $-2$ 枚硬币。对她来说最优策略是停留在原地，结束时拥有 $0$ 枚硬币。

:::align{center} :::

在附加样例 #1 中，Ada 从交叉点 $(1, 3)$ 出发，初始有 $0$ 枚硬币。她可以通过以下步骤获得最大硬币数：

• 向西移动到 $(1, 2)$。使用向西的通行费函数 $F_{\text{西}} = c \times 1$，Ada 现有 $0 \times 1 = 0$ 枚硬币。
• 暂不配送 $(1, 2)$ 处的披萨，向南移动到 $(2, 2)$。使用向南的通行费函数 $F_{\text{南}} = c / 4$，Ada 现有 $0 / 4 = 0$ 枚硬币。
• 向北移动到 $(1, 2)$。使用向北的通行费函数 $F_{\text{北}} = c + 4$，Ada 现有 $0 + 4 = 4$ 枚硬币。
• 配送 $(1, 2)$ 处的披萨。Ada 获得 $4$ 枚额外硬币，最终共有 $8$ 枚硬币。

在附加样例 #2 中，Ada 无法在 $1$ 分钟内配送 $2$ 份披萨，因此输出 IMPOSSIBLE。

在附加样例 #3 中，Ada 从交叉点 $(1, 3)$ 出发，初始有 $0$ 枚硬币。她可以通过以下步骤获得最大硬币数：

• 向西移动到 $(1, 2)$。使用向西的通行费函数 $F_{\text{西}} = c - 3$，Ada 现有 $0 - 3 = -3$ 枚硬币。
• 向南移动到 $(2, 2)$。使用向南的通行费函数 $F_{\text{南}} = c / 4$，Ada 现有 $\lfloor -3 / 4 \rfloor = -1$ 枚硬币。
• 配送 $(2, 2)$ 处的披萨。Ada 获得 $2$ 枚额外硬币，最终共有 $1$ 枚硬币。

限制条件

$1 \le T \le 100$。

$1 \le N \le 10$。

$1 \le M \le 20$。

$1 \le A_r, A_c \le N$。

对于所有 $k$，$1 \le X_k, Y_k \le N$。

对于所有 $k$，$1 \le C_k \le 4$。

对于所有 $d$，$1 \le K_d \le 4$。

对于所有 $d$，$\mathrm{OP}_d$ 是 $(+, -, *, /)$ 之一。

保证没有顾客位于 Ada 的起始交叉点，即对于所有 $1 \le k \le P$，有 $(X_k, Y_k) \ne (A_r, A_c)$。

保证每位顾客位于不同的交叉点，即对于所有 $1 \le k, l \le P$ 且 $k \ne l$，有 $(X_k, Y_k) \ne (X_l, Y_l)$。

测试集 1

$P = 0$。

测试集 2

$0 \le P \le 10$。

翻译由 DeepSeek V4 Pro 完成