Balloon Recovery

Company G has released many balloons into the sky. To service a balloon, the company has to collect it at its tower, which stands at horizontal position $0$. Balloon $i$ is at horizontal position $P_i$ and height $H_i$.

The engineers raise and lower a balloon by radio, telling it to drop ballast or let out air. They cannot move a balloon horizontally, so it depends on the wind at its height.

A balloon can sit at $M$ heights, numbered $0$ to $M-1$. The wind at height $j$ has velocity $V_j$. A positive $V_j$ means the wind blows from left to right, and a negative $V_j$ means it blows from right to left. A balloon at position $P$ that stays at a height with wind velocity $V$ is at position $P + tV$ after time $t$. Time runs continuously, so $t$ can be any real number. The moment a balloon's position becomes $0$, it is collected.

Moving one balloon from height $a$ to height $b$ costs $|a - b|$ energy. A height change takes no time, and you may change a balloon's height at any moment and as many times as you want. You have $Q$ energy for all balloons together, and you do not have to spend all of it.

Find the time it takes to collect every balloon when you spend the energy optimally. Time is counted in whole units: the answer is the smallest integer that is greater than or equal to the earliest moment by which every balloon is collected. If the last balloon is collected at time $1.5$, the answer is $2$.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of balloons $N$, the number of heights $M$, and the available energy $Q$, separated by spaces. The second line contains $M$ integers, where the $j$th value (counting from $0$) is the wind velocity $V_j$ at height $j$. Each of the next $N$ lines contains the position $P_i$ and the height $H_i$ of balloon $i$.

Limits

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

For each test case, print one line in the form "Case #x: y". Here $x$ is the test case number starting from $1$, and $y$ is the minimum time needed to collect every balloon. If the given energy is not enough to collect every balloon, print IMPOSSIBLE in place of $y$.

In the first test case of the first example there are two balloons and $1$ energy point. The best move is to spend that point lowering the balloon at position $3$, height $3$ to height $2$. The wind at height $2$ has velocity $-2$, so that balloon reaches the tower at time $1.5$. The balloon at position $-2$, height $1$ rides a wind of velocity $1$ and reaches the tower at time $2$. Both balloons are collected by time $2$, so the answer is $2$.