gBalloon (Small)

Problem

Company G keeps many balloons in the air. To service them, the balloons have to be brought back to the company tower, which stands at horizontal position 0. Balloon $i$ is now at horizontal position $P_i$ and height $H_i$ .

The engineers at G can only change the height of a balloon, by sending a radio signal that drops ballast or lets air out. They cannot push a balloon sideways, so horizontal motion is left to the wind.

A balloon can be at one of $M$ heights, numbered 0 to $M-1$ . The wind differs from height to height. At height $j$ the wind has velocity $V_j$ : a positive value blows from left to right, a negative value from right to left. A balloon that stays at height $j$ and starts at position $P$ is at $P + V_j$ after one time unit and at $P + 2V_j$ after two time units. The balloon drifts at a constant speed inside a time unit as well, and the moment its position becomes 0 it touches the tower and is collected right away. A balloon that passes 0 in the middle of a time unit is collected at that moment.

Changing a height takes no time but costs energy. Moving one balloon from height $H_{\text{old}}$ to height $H_{\text{new}}$ costs $|H_{\text{old}} - H_{\text{new}}|$ energy. Heights may be changed only at integer times, that is at time 0 and at the end of each time unit, and there is no limit on the number of changes. All balloons draw from one budget of $Q$ energy, and you do not have to spend all of it.

Spend the energy in the best possible way and find how long it takes to collect every balloon.

Input

The first line holds the number of test cases $T$ . The first line of each test case holds the number of balloons $N$ , the number of heights $M$ , and the available energy $Q$ .

The second line holds $M$ integers. The $j$ th value on this line, counting from 0, is the wind velocity $V_j$ at height $j$ .

Each of the next $N$ lines holds the horizontal position $P_i$ and the height $H_i$ of one balloon.

Limits

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

Output

For each test case, print one line in the form Case #x: y. $x$ is the test case number, starting from 1, and $y$ is the smallest integer such that every balloon is collected no later than time $y$ . If the given energy is not enough to collect every balloon, print IMPOSSIBLE in place of $y$ .

Note

The first sample case has two balloons and 1 unit of energy. The best plan is to spend that unit at the start and drop the balloon at position 3, height 3 down to height 2. The wind at height 2 has velocity $-2$ , so this balloon drifts from position 3 to 1 and then from 1 to $-1$ , passing position 0 in the middle of the second time unit. The balloon at position $-2$ , height 1 rides a wind of velocity 1 and reaches position 0 at time unit 2. Collecting both balloons therefore takes 2 time units.