병아리 태우기

병아리 떼가 곧고 좁은 길을 따라 동쪽으로 달리고 있다. 각 병아리는 저마다 일정한 속도로 달린다. 병아리가 앞에 있는 병아리를 따라잡을 때마다 속도를 늦추고 그 병아리의 속도로 뒤따라가야 한다. 당신은 병아리 떼 뒤의 이동식 크레인에 타고 길 끝의 헛간을 향해 병아리들을 쫓고 있다. 크레인의 팔을 이용하면 임의의 병아리를 잠시 들어 올려 그 뒤의 병아리가 아래로 지나가게 한 다음, 들어 올린 병아리를 다시 내려놓을 수 있다. 이 작업에는 시간이 걸리지 않으며, 3마리 이상의 병아리가 한 줄로 차례차례 늘어서 있더라도 서로 바로 인접한 병아리 한 쌍에 대해서만 수행할 수 있다.

시각 0에서 병아리들의 초기 위치($X_{i}$)와 원래 속도($V_{i}$), 그리고 헛간의 위치(B)가 주어질 때, N마리의 병아리 중 적어도 K마리가 시각 T 이내에 헛간에 도착하게 하기 위해 크레인으로 수행해야 하는 교환의 최소 횟수는 얼마인가?

병아리들을 직선 위에서 움직이는 점으로 생각해도 된다. 3마리 이상의 병아리가 같은 위치에 서로 인접해 있더라도, 그중 하나를 들어 올리면 다른 둘 중 하나만 그 아래로 지나갈 수 있다. 모든 교환은 순간적으로 이루어지므로 여러 교환을 동시에 수행할 수 있지만, 각각은 별도의 교환으로 센다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ C ≤ 100; 1 ≤ B ≤ 1,000,000,000; 1 ≤ T ≤ 1,000; 0 ≤ $X_{i}$ < B; 1 ≤ $V_{i}$ ≤ 100; 모든 $X_{i}$는 서로 다르며 증가하는 순서로 주어진다.

작은 데이터셋 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10; 0 ≤ K ≤ min(3, N);

큰 데이터셋 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 50; 0 ≤ K ≤ N;

입력의 첫 번째 줄에는 테스트 케이스의 수 C가 주어진다. 이어서 C개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 주어지는 4개의 정수 N, K, B, T로 시작한다. 다음 줄에는 서로 다른 N개의 정수 $X_{i}$가 증가하는 순서로 주어진다. 그다음 줄에는 N개의 정수 $V_{i}$가 주어진다. 모든 거리는 미터 단위이고, 모든 속도는 초당 미터 단위이며, 모든 시간은 초 단위이다.

각 테스트 케이스마다 "Case #x: S"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이고(1부터 시작), S는 필요한 최소 교환 횟수이며, 불가능한 경우에는 단어 "IMPOSSIBLE"을 출력한다.