Picking Up Chicks

A flock of chicks runs east along a straight, narrow road. Each chick runs at its own constant speed. When a chick catches up to the chick in front of it, it slows down and follows at the speed of that chick.

You drive a mobile crane behind the flock and push the chicks toward the barn at the end of the road. The crane arm can lift one chick for an instant, let the chick right behind it pass underneath, and set the lifted chick back down. The operation takes no time, and you can apply it only to a pair of chicks that stand next to each other in the line, even when three or more chicks are bunched together.

You are given the position $X_i$ of every chick at time 0, its natural speed $V_i$, and the position $B$ of the barn. Find the smallest number of lifts you need so that at least $K$ of the $N$ chicks reach the barn no later than time $T$.

Treat the chicks as points on a line. Even when three or more chicks stand at the same position in a row, lifting one of them lets only one of the other two pass. Every lift is instantaneous, so several lifts may happen at the same moment, and each one counts separately.

The first line contains the number of test cases $C$. Each test case takes three lines. The first line has four integers $N$, $K$, $B$ and $T$. The second line has the $N$ distinct integers $X_i$ in increasing order. The third line has the $N$ integers $V_i$. Distances are in meters, speeds in meters per second, and times in seconds.

Limits

• $1 \le C \le 100$
• $1 \le N \le 50$
• $0 \le K \le N$
• $1 \le B \le 10^9$
• $1 \le T \le 1000$
• $0 \le X_i < B$
• $1 \le V_i \le 100$
• every $X_i$ is distinct and the values are given in increasing order

For each test case, print one line of the form Case #x: S, where x is the test case number starting from 1 and $S$ is the smallest number of lifts. When fewer than $K$ chicks can reach the barn by time $T$, print the word IMPOSSIBLE in place of $S$.