题目描述

The G tech company has deployed many balloons. Sometimes, they need to be collected for maintenance at the company's tower, which is located at horizontal position $0$. Each balloon is currently at horizontal position $P_i$ and height $H_i$.

G engineers can move a balloon up and down by sending radio signals to tell it to drop ballast or let out air. But they can't move the balloon horizontally; they have to rely on existing winds to do that.

There are $M$ different heights where the balloons could be. The winds at different heights may blow in different directions and at different velocities. Specifically, at height $j$, the wind has velocity $V_j$, with positive velocities meaning that the wind blows left to right, and negative velocities meaning that the wind blows right to left. A balloon at position $P$ at a height with wind velocity $V$ will be at position $P+V$ after one time unit, $P+2V$ after two time units, etc. If a balloon touches the tower, it is immediately collected.

It costs $| H_{\text{original}} - H_{\text{new}} |$ points of energy to move one balloon between two different heights. (This transfer takes no time.) You have $Q$ points of energy to spend, although you do not need to spend all of it. What is the least amount of time it will take to collect all the balloons, if you spend energy optimally?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follows. The first line of each case has three integers $N$, $M$, and $Q$, representing the number of balloons, the number of height levels, and the amount of energy available.

The second line has $M$ integers; the $j$th value on this line (counting starting from $0$) is the wind velocity at height $j$.

Then, $N$ more lines follow. The $i$th of these lines consists of two integers, $P_i$ and $H_i$, representing the position and height of the $i$th balloon.

输出格式

For each test case, output one line containing "Case #x: y", where $x$ is the test case number (starting from 1) and $y$ is the minimum number of time units needed to collect all of the balloons, returns IMPOSSIBLE if it's impossible to collect all the balloons using the energy given.

2
2 4 1
2 1 -2 -1
3 3
-2 1
1 3 1
1 -1 -2
-2 2

Case #1: 2
Case #2: IMPOSSIBLE

提示

Here is an example:

:::align{center} :::

In the sample case, there are $2$ balloons in the sky, and you have $1$ energy point to use. The best solution is to immediately spend $1$ energy point to move the balloon at position $3$, height $3$ down to height $2$. Once you've done that, it will take $2$ time units for both balloons to reach the tower.

Limits

Small dataset (Test Set 1 - Visible)

$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$.

Large dataset (Test Set 2 - Hidden)

$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$.