Problem Description

Ada delivers pizzas in a city consisting of a grid of $N$ horizontal and $N$ vertical streets, heading from North to South and from West to East, respectively, and numbered from $1$ to $N$. The top left street crossing of the grid is $(1, 1)$.

Today, Ada has to deliver $P$ pizzas, one for each of $P$ customers. Each customer lives at a different street crossing; the $k$-th customer lives at street crossing $(X_k, Y_k)$ and will pay Ada $C_k$ coins after the pizza is delivered to their location.

Ada starts at her pizza restaurant at $(A_r, A_c)$ with $0$ coins and carrying $P$ pizzas. Her goal is to deliver all of the pizzas within $M$ minutes. She is free to take any path she likes around the city and finish deliveries anywhere, as long as she manages to drop off all $P$ pizzas to their respective customers within $M$ minutes. It takes $1$ minute to walk between $2$ adjacent street crossings, and takes no additional time to drop off a pizza at a customer's location. There are some additional rules and constraints to note:

• Ada is not allowed to go outside the grid.
• No customer lives at the same street crossing as the pizza restaurant Ada starts her trip.
• At any point in time Ada can choose to stay in her current location and not move.
• Ada can also choose not to deliver a pizza when at a customer's location.

Formally, if Ada is currently at street crossing $(i, j)$, where $i$ is the $i$-th row from the top, and $j$ is the $j$-th column from the left, she can decide to do any of the following as long as she does not go outside the grid:

• Go north, she reaches street crossing $(i - 1, j)$.
• Go east, she reaches street crossing $(i, j + 1)$.
• Go west, she reaches street crossing $(i, j - 1)$.
• Go south, she reaches street crossing $(i + 1, j)$.
• Stay at street crossing $(i, j)$.

:::align{center} :::

The city has a unique toll system in place for using the streets. There is a toll for using each street and the toll depends on Ada's current number of coins and the direction in which she is travelling to. The toll function is defined for every cardinal direction (North, East, West, South) separately. The toll function $F_d$ for $d \in \{\text{North}, \text{East}, \text{West}, \text{South}\}$ returns the amount of coins Ada will have after moving in the direction $d$ and is defined as follows:

where $c$ is the current number of coins that Ada has and $\mathrm{OP}_d$ is an operator and $K_d$ is a fixed positive integer. The allowed operators are:

• $+$ (addition),
• $-$ (subtraction),
• $\times$ (multiplication),
• $/$ (integer division).

For example, we can have $F_{\text{North}} = c + 3$, $F_{\text{East}} = c \times 4$, $F_{\text{West}} = c - 4$, $F_{\text{South}} = c / 2$.

That means that if Ada moves North one street then she will have $3$ more coins; if Ada moves East then Ada's coins will quadruple; if Ada moves West then she loses $4$ coins; and if Ada moves South then her coins are halved.

All divisions are integer divisions and are computed by using floor function. For example,

Notice that Ada is allowed to have a negative number of coins. Note that the tolls might actually give Ada coins.

Find out if Ada can deliver all the $P$ pizzas in $M$ minutes and, if so, the maximum number of coins Ada could have after $M$ minutes.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains $N$, $P$, $M$, $A_r$, $A_c$ denoting the grid size, the number of pizzas to deliver, the minutes in which all pizzas should be delivered, and the coordinates of the street crossing at which Ada starts respectively.

The next $4$ lines denote the toll functions for North, East, West, South respectively. Each of these lines contains $\mathrm{OP}_d$, denoting the operator (one of $+$, $-$, $*$, $/$), and $K_d$, the positive integer used in toll function.

The following $P$ lines describe the customers. Each of these lines consists of $3$ integers $X_k$, $Y_k$, $C_k$ denoting the row number of the $k$-th customer from the top of the grid, the column number of the $k$-th customer from the left of the grid, and the amount of coins they pay on delivery, respectively.

Output Format

For each test case, output one line containing Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is IMPOSSIBLE if all pizzas cannot be delivered within $M$ minutes; otherwise, the output should be the maximum number of coins Ada can have after $M$ minutes, which could be negative.

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

Hint

In Sample Case #$1$, Ada does not deliver any pizzas. Ada is located at street crossing $(1, 2)$. In $1$ minute she can decide to move west and go to $(1, 1)$, so that the toll at $(1, 2)$ calculates Ada's coins using the toll function $F_{\text{West}} = c + 3$, which results in $3$ coins. Therefore Ada can have maximum of $3$ coins with her after $1$ minute.

In Sample Case #$2$, Ada does not deliver any pizzas. Ada is located at street crossing $(2, 3)$. All directions have a similar toll function, $F_d = c - 2$ for all $d$. If she decides to go in any direction, she will end up with $-2$ coins. It is optimal for Ada to stay at the same location and have $0$ coins at the end.

:::align{center} :::

In Additional Sample Case #$1$, Ada started at street crossing $(1, 3)$ with $0$ coins. Ada can receive maximum coins by following the steps below:

• Go west to $(1, 2)$. Using the toll function for moving west $F_{\text{west}} = c \times 1$, Ada now has $0 \times 1 = 0$ coins.
• Do not deliver the pizza at $(1, 2)$ yet, and go south to $(2, 2)$. Using the toll function for moving south $F_{\text{South}} = c / 4$, Ada now has $0 / 4 = 0$ coins.
• Go north to $(1, 2)$. Using the toll function for moving north $F_{\text{North}} = c + 4$, Ada now has $0 + 4 = 4$ coins.
• Deliver the pizza at $(1, 2)$. Ada receives $4$ additional coins for delivering the pizza. Ada has a total of $8$ coins in the end.

In Additional Sample Case #$2$, Ada cannot deliver $2$ pizzas in $1$ minute, so the output is IMPOSSIBLE.

In Additional Sample Case #$3$, Ada started at street crossing $(1, 3)$ with $0$ coins. Ada can receive maximum coins by following the steps below:

• Go west to $(1, 2)$. Using the toll function for moving west $F_{\text{West}} = c - 3$, Ada now has $0 - 3 = -3$ coins.
• Go south to $(2, 2)$. Using the toll function for moving south $F_{\text{South}} = c / 4$, Ada now has $-3 / 4 = \lfloor \frac{-3}{4} \rfloor = -1$ coins.
• Deliver the pizza at $(2, 2)$. Ada receives $2$ additional coins for delivering the pizza. Ada has a total of $1$ coins in the end.

Limits

$1 \le T \le 100$.

$1 \le N \le 10$.

$1 \le M \le 20$.

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

$1 \le X_k, Y_k \le N$, for all $k$.

$1 \le C_k \le 4$, for all $k$.

$1 \le K_d \le 4$, for all $d$.

$\mathrm{OP}_d$ is one of $(+, -, *, /)$, for all $d$.

It is guaranteed that no customer lives at the same street crossing as the pizza restaurant Ada starts her trip, i.e. $(X_k, Y_k) \ne (A_r, A_c)$, for all $1 \le k \le P$.

It is guaranteed that every customer lives at a different street crossing, i.e. $(X_k, Y_k) \ne (X_l, Y_l)$, for all $1 \le k, l \le P$ and $k \ne l$.

Test Set $1$

$P = 0$.

Test Set $2$

$0 \le P \le 10$.