기구 회수

G사는 하늘에 기구를 여러 개 띄워 두었다. 정비를 하려면 기구를 회수해야 하는데, 회수 지점은 가로 좌표 $0$에 서 있는 회사 탑이다. $i$번 기구는 가로 좌표 $P_i$, 높이 $H_i$에 떠 있다.

기술진은 무선 신호를 보내 기구가 모래주머니를 버리거나 공기를 빼도록 해서 기구를 올리고 내린다. 가로 방향으로는 기구를 직접 움직이지 못하고, 그 높이에 부는 바람에만 의존한다.

기구가 머무를 수 있는 높이는 $M$개이고 $0$번부터 $M-1$번까지 번호가 붙어 있다. 높이 $j$에 부는 바람의 속도는 $V_j$이다. $V_j$가 양수면 바람이 왼쪽에서 오른쪽으로 불고, 음수면 오른쪽에서 왼쪽으로 분다. 좌표 $P$에 있는 기구가 속도 $V$인 높이에 계속 머무르면 시간 $t$가 흐른 뒤 좌표는 $P + tV$가 된다. 시간은 연속으로 흐르므로 $t$는 실수일 수 있다. 기구의 좌표가 $0$이 되는 순간 그 기구는 바로 회수된다.

기구 하나를 높이 $a$에서 높이 $b$로 옮기는 데는 에너지 $|a - b|$가 든다. 높이를 바꾸는 데 시간은 들지 않고, 원하는 시각에 몇 번이든 바꿀 수 있다. 쓸 수 있는 에너지는 기구 전체를 통틀어 $Q$이며, 전부 쓰지 않아도 된다.

에너지를 가장 잘 써서 모든 기구를 회수할 때 걸리는 시간을 구하라. 시간은 정수 단위로 센다. 즉 모든 기구가 회수되는 가장 이른 시각보다 크거나 같은 정수 중 가장 작은 값이 답이다. 마지막 기구가 시각 $1.5$에 회수되면 답은 $2$이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 기구의 수 $N$, 높이의 개수 $M$, 쓸 수 있는 에너지 $Q$가 공백으로 구분되어 주어진다. 둘째 줄에는 $M$개의 정수가 주어지며, 그중 $j$번째 값($0$부터 센다)이 높이 $j$의 바람 속도 $V_j$이다. 이어지는 $N$개의 줄에는 각각 $i$번 기구의 좌표 $P_i$와 높이 $H_i$가 주어진다.

제한

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 $1$부터 시작한다. $y$는 모든 기구를 회수하는 데 걸리는 시간의 최솟값이다. 주어진 에너지로 모든 기구를 회수할 수 없다면 $y$ 자리에 IMPOSSIBLE을 출력한다.

첫 번째 예제의 첫 테스트 케이스에는 기구가 두 개 있고 에너지는 $1$이다. 좌표 $3$, 높이 $3$에 있는 기구를 에너지 $1$을 써서 높이 $2$로 내리는 것이 가장 좋다. 높이 $2$의 바람 속도가 $-2$이므로 이 기구는 시각 $1.5$에 탑에 닿는다. 좌표 $-2$, 높이 $1$에 있는 기구는 속도 $1$인 바람을 타고 시각 $2$에 탑에 닿는다. 두 기구가 모두 회수되는 가장 이른 시각이 $2$이므로 답은 $2$이다.