피자 배달

Ada는 각각 북쪽에서 남쪽으로, 서쪽에서 동쪽으로 뻗어 있으며 $1$부터 $\mathbf{N}$까지 번호가 매겨진 $\mathbf{N}$개의 수평 도로와 $\mathbf{N}$개의 수직 도로로 이루어진 격자형 도시에서 피자를 배달한다. 격자의 왼쪽 위 교차로는 $(1,1)$이다.

오늘 Ada는 $\mathbf{P}$명의 고객 각각에게 하나씩, 피자 $\mathbf{P}$개를 배달해야 한다. 각 고객은 서로 다른 교차로에 산다. $k$번째 고객은 교차로 $(\mathbf{X_k}, \mathbf{Y_k})$에 살며, 자신의 위치로 피자가 배달되면 Ada에게 동전 $\mathbf{C_k}$개를 지불한다.

Ada는 피자 가게 $(\mathbf{A_r}, \mathbf{A_c})$에서 동전 $0$개와 피자 $\mathbf{P}$개를 가지고 출발한다. Ada의 목표는 $\mathbf{M}$분 이내에 모든 피자를 배달하는 것이다. Ada는 $\mathbf{M}$분 이내에 피자 $\mathbf{P}$개를 각 고객에게 모두 전달할 수만 있다면, 도시에서 원하는 어떤 경로로든 이동하고 어디에서든 배달을 마쳐도 된다. 인접한 두 교차로 사이를 걷는 데에는 1분이 걸리고, 고객의 위치에서 피자를 전달하는 데에는 추가 시간이 걸리지 않는다. 다음과 같은 추가 규칙과 제약 조건에 유의해야 한다.

• Ada는 격자 밖으로 나갈 수 없다.

• Ada가 이동을 시작하는 피자 가게와 같은 교차로에 사는 고객은 없다.

• Ada는 어느 시점에서든 현재 위치에 머물며 이동하지 않기로 선택할 수 있다.

• Ada는 고객의 위치에 있더라도 피자를 배달하지 않기로 선택할 수도 있다.

형식적으로, Ada가 현재 교차로 $(i,j)$에 있고, 여기서 $i$은 위에서부터 $i$번째 행이고 $j$은 왼쪽에서부터 $j$번째 열이라면, 격자 밖으로 나가지 않는 한 다음 중 어느 것이든 수행할 수 있다.

• 북쪽으로 이동하여 교차로 $(i-1, j)$에 도착한다.

• 동쪽으로 이동하여 교차로 $(i, j+1)$에 도착한다.

• 서쪽으로 이동하여 교차로 $(i, j-1)$에 도착한다.

• 남쪽으로 이동하여 교차로 $(i+1, j)$에 도착한다.

• 교차로 $(i, j)$에 머문다.

이 도시에는 도로 이용을 위한 독특한 통행료 체계가 있다. 각 도로를 이용할 때 통행료가 적용되며, 통행료는 Ada가 현재 가진 동전의 수와 이동 방향에 따라 달라진다. 통행료 함수는 각 방위(북쪽, 동쪽, 서쪽, 남쪽)에 대해 별도로 정의된다. $d \in \{ North, East, West, South \}$에 대한 통행료 함수 $F_d$는 Ada가 $d$ 방향으로 이동한 뒤 가지게 될 동전의 수를 반환하며, 다음과 같이 정의된다.

$F_d$ = $c$ $\mathbf{OP_d}$ $\mathbf{K_d}$

여기서 $c$은 Ada가 현재 가진 동전의 수이고, $\mathbf{OP_d}$는 연산자이며, $\mathbf{K_d}$은 고정된 양의 정수이다. 허용되는 연산자는 다음과 같다.

• + (덧셈),

• - (뺄셈),

• * (곱셈),

• / (정수 나눗셈).

예를 들어 $F_{North}$ = $c$ + $3$, $F_{East}$ = $c$ * $4$, $F_{West}$ = $c$ - $4$, $F_{South}$ = $c$ / $2$일 수 있다. 이는 Ada가 북쪽으로 한 도로만큼 이동하면 동전이 $3$개 늘어나고, 동쪽으로 이동하면 동전 수가 네 배가 되며, 서쪽으로 이동하면 동전 $4$개를 잃고, 남쪽으로 이동하면 동전 수가 절반이 된다는 뜻이다.

모든 나눗셈은 정수 나눗셈이며 바닥 함수를 사용하여 계산한다. 예를 들어 $\frac{-1}{4} = \lfloor\frac{-1}{4}\rfloor = -1$이다. Ada가 음수 개의 동전을 가질 수도 있음에 유의하라. 통행료로 인해 오히려 Ada가 동전을 얻을 수도 있음에도 유의하라.

Ada가 $\mathbf{M}$분 이내에 피자 $\mathbf{P}$개를 모두 배달할 수 있는지 알아내고, 가능하다면 $\mathbf{M}$분 후 Ada가 가질 수 있는 동전의 최대 개수를 구하라.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 10$. $1 \le \mathbf{M} \le 20$. $1 \le \mathbf{A_r}, \mathbf{A_c} \le \mathbf{N}$. 모든 $k$에 대해 $1 \le \mathbf{X_k}, \mathbf{Y_k} \le \mathbf{N}$. 모든 $k$에 대해 $1 \le \mathbf{C_k} \le 4$. 모든 $d$에 대해 $1 \le \mathbf{K_d} \le 4$. 모든 $d$에 대해 $\mathbf{OP_d}$는 (+, -, *, /) 중 하나이다. 모든 $1 \le k \le \mathbf{P}$에 대해 $(\mathbf{X_k}, \mathbf{Y_k}) \neq (\mathbf{A_r}, \mathbf{A_c})$이다. 즉, Ada가 이동을 시작하는 피자 가게와 같은 교차로에 사는 고객은 없음이 보장된다. 모든 $1 \le k, l \le \mathbf{P}$와 $k \neq l$에 대해 $(`X_k, \mathbf{Y_k}) \neq (\mathbf{X_l}, \mathbf{Y_l})$이다. 즉, 모든 고객이 서로 다른 교차로에 사는 것이 보장된다.

테스트 세트 1

$\mathbf{P} = 0$.

테스트 세트 2

$0 \le \mathbf{P} \le 10$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 $\mathbf{N}$, $\mathbf{P}$, $\mathbf{M}$, $\mathbf{A_r}$, $\mathbf{A_c}$가 주어지며, 각각 격자의 크기, 배달할 피자의 수, 모든 피자를 배달해야 하는 시간(분), Ada가 출발하는 교차로의 좌표를 나타낸다.

다음 네 줄은 각각 북쪽, 동쪽, 서쪽, 남쪽에 대한 통행료 함수를 나타낸다. 각 줄에는 연산자(+, -, *, / 중 하나)를 나타내는 $\mathbf{OP_d}$와 통행료 함수에 사용되는 양의 정수 $\mathbf{K_d}$이 주어진다.

이어지는 $\mathbf{P}$개의 줄은 고객을 설명한다. 각 줄은 세 정수 $\mathbf{X_k}$, $\mathbf{Y_k}$, $\mathbf{C_k}$로 이루어지며, 각각 $k$번째 고객이 있는 격자의 위에서부터의 행 번호, $k$번째 고객이 있는 격자의 왼쪽에서부터의 열 번호, 그리고 배달 시 지불하는 동전의 수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), 모든 피자를 $\mathbf{M}$분 이내에 배달할 수 없다면 $y$은 IMPOSSIBLE이다. 그렇지 않다면 $\mathbf{M}$분 후 Ada가 가질 수 있는 동전의 최대 개수(음수일 수도 있음)를 출력해야 한다.

샘플 케이스 #1에서 Ada는 어떤 피자도 배달하지 않는다. Ada는 교차로 $(1,2)$에 있다. $1$분 동안 Ada는 서쪽으로 이동하여 $(1,1)$로 가기로 할 수 있으며, 그러면 $(1,2)$에서의 통행료가 통행료 함수 F_{West} = $c$ + $3$를 사용해 Ada의 동전을 계산하여 동전 수가 $3$개가 된다. Therefore Ada는 $1$분 후 최대 동전 $3$개를 가질 수 있다.

샘플 케이스 #2에서 Ada는 어떤 피자도 배달하지 않는다. Ada는 교차로 $(2, 3)$에 있다. 모든 방향의 통행료 함수는 유사하며, 모든 $d$에 대해 $F_d$ = $c$ - $2$이다. 어느 방향으로든 이동하기로 하면 동전이 $-2$개가 된다. Ada에게는 같은 위치에 머물러 마지막에 동전 $0$개를 가지는 것이 최적이다.

추가 샘플 - 테스트 세트 2

추가 샘플 케이스 #1에서 Ada는 동전 $0$개를 가지고 교차로 $(1,3)$에서 출발했다. Ada는 아래 단계를 따르면 최대 개수의 동전을 얻을 수 있다.

• 서쪽의 $(1,2)$로 이동한다. 서쪽 이동에 대한 통행료 함수 $F_{west}$ = $c$ * $1$를 사용하면, 이제 Ada는 동전 $0 * 1 = 0$개를 가진다.

• 아직 $(1,2)$에서 피자를 배달하지 않고, 남쪽의 $(2,2)$로 이동한다. 남쪽 이동에 대한 통행료 함수 $F_{South}$ = $c$ / $4$를 사용하면, 이제 Ada는 동전 $0 / 4 = 0$개를 가진다.

• 북쪽의 $(1,2)$로 이동한다. 북쪽 이동에 대한 통행료 함수 $F_{North}$ = $c$ + $4$를 사용하면, 이제 Ada는 동전 $0 + 4 = 4$개를 가진다.

• $(1,2)$에서 피자를 배달한다. Ada는 피자를 배달하여 동전 $4$개를 추가로 받는다. 마지막에 Ada는 총 동전 $8$개를 가진다.

추가 샘플 케이스 #2에서 Ada는 한 분 안에 피자 두 개를 배달할 수 없으므로 출력은 IMPOSSIBLE이다.

추가 샘플 케이스 #3에서 Ada는 동전 $0$개를 가지고 교차로 $(1,3)$에서 출발했다. Ada는 아래 단계를 따르면 최대 개수의 동전을 얻을 수 있다.

• 서쪽의 $(1,2)$로 이동한다. 서쪽 이동에 대한 통행료 함수 $F_{West}$ = $c$ - $3$를 사용하면, 이제 Ada는 동전 $0 - 3 = -3$개를 가진다.

• 남쪽의 $(2,2)$로 이동한다. 남쪽 이동에 대한 통행료 함수 $F_{South}$ = $c$ / $4$를 사용하면, 이제 Ada는 동전 $-3 / 4 = \lfloor\frac{-3}{4}\rfloor = -1$개를 가진다.

• $(2,2)$에서 피자를 배달한다. Ada는 피자를 배달하여 동전 $2$개를 추가로 받는다. 마지막에 Ada는 총 동전 $1$개를 가진다.