gBalloon

G 기술 회사는 많은 풍선을 배치했다. 때때로 정비를 위해 이 풍선들을 회사의 탑으로 회수해야 하며, 이 탑은 수평 위치 0에 있다. 각 풍선은 현재 수평 위치 $P_{i}$와 높이 $H_{i}$에 있다.

G의 엔지니어들은 풍선에 무선 신호를 보내 밸러스트를 버리거나 공기를 빼도록 지시함으로써 풍선을 위아래로 움직일 수 있다. 그러나 풍선을 수평으로 움직일 수는 없으므로, 이를 위해서는 이미 존재하는 바람에 의존해야 한다.

풍선이 있을 수 있는 높이는 서로 다른 M개이다. 높이에 따라 바람이 서로 다른 방향과 속도로 불 수 있다. 구체적으로 높이 j에서 바람의 속도는 $V_{j}$이며, 양의 속도는 바람이 왼쪽에서 오른쪽으로 분다는 뜻이고 음의 속도는 바람이 오른쪽에서 왼쪽으로 분다는 뜻이다. 위치 P에서 풍속이 V인 높이에 있는 풍선은 한 시간 단위 후에 위치 P+V에, 두 시간 단위 후에 위치 P+2V에 있게 되며, 이후에도 같은 방식으로 이동한다. 풍선이 탑에 닿으면 즉시 회수된다.

풍선 하나를 서로 다른 두 높이 사이에서 이동시키는 데 | $H_{original}$ - $H_{new}$ |점의 에너지가 든다. (이 이동에는 시간이 걸리지 않는다.) 사용할 수 있는 에너지는 Q점이지만, 이를 모두 사용할 필요는 없다. 에너지를 최적으로 사용한다면 모든 풍선을 회수하는 데 걸리는 최소 시간은 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB.

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

1 ≤ T ≤ 100. 1 ≤ N ≤ 10. 1 ≤ M ≤ 10. -10 ≤ $V_{j}$ ≤ 10. 1 ≤ Q ≤ 10. 0 ≤ $H_{i}$ <M. -10 ≤ $P_{i}$ ≤ 10.

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

1 ≤ T ≤ 25. 1 ≤ N ≤ 100. 1 ≤ M ≤ 1000. -100 ≤ $V_{j}$ ≤ 100. 1 ≤ Q ≤ 10000 0 ≤ $H_{i}$ <M. -10000 ≤ $P_{i}$ ≤ 10000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 풍선의 수, 높이 단계의 수, 사용할 수 있는 에너지의 양을 각각 나타내는 세 정수 N, M, Q가 주어진다. 두 번째 줄에는 M개의 정수가 주어진다. 이 줄의 j번째 값(0부터 세기 시작)은 높이 j에서의 풍속이다. 이어서 N개의 줄이 더 주어진다. 이 중 i번째 줄은 두 정수 $P_{i}$와 $H_{i}$로 이루어지며, 각각 i번째 풍선의 위치와 높이를 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 모든 풍선을 회수하는 데 필요한 최소 시간 단위 수이다. 주어진 에너지를 사용하여 모든 풍선을 회수할 수 없다면 IMPOSSIBLE를 반환한다.

다음은 예제이다.

예제 케이스에서는 하늘에 풍선 두 개가 있고, 사용할 수 있는 에너지는 1점이다. 최적의 방법은 즉시 에너지 1점을 사용하여 위치 3, 높이 3에 있는 풍선을 높이 2까지 아래로 이동시키는 것이다. 그렇게 하고 나면 두 풍선이 모두 탑에 도달하는 데 2시간 단위가 걸린다.