cho.sh

gBalloon (작은 입력)

층마다 다른 바람 속에서 높이 변경 비용 합이 Q를 넘지 않게 나누어 모든 풍선을 위치 0에 가장 빨리 모으는 시간을 구합니다.

보통6동적 계획법이분 탐색아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

G사는 하늘에 기구를 여러 대 띄워 두었다. 정비를 하려면 기구를 회사 관제탑으로 모아야 한다. 관제탑은 수평 좌표 0에 서 있다. ii번째 기구는 지금 수평 좌표 PiP_i, 높이 HiH_i에 있다.

G사 기술진은 무선 신호를 보내 밸러스트를 버리거나 기체를 빼내는 방법으로 기구의 높이만 바꿀 수 있다. 수평 방향으로는 직접 밀지 못하므로 옆으로 움직이는 일은 바람에 맡긴다.

기구가 있을 수 있는 높이는 MM가지이고 0번부터 M−1M-1번까지 번호가 붙어 있다. 높이마다 바람의 방향과 속도가 다르다. 높이 jj의 바람 속도는 VjV_j이며, 값이 양수면 왼쪽에서 오른쪽으로, 음수면 오른쪽에서 왼쪽으로 분다. 높이 jj에 계속 머무는 기구가 좌표 PP에서 출발하면 한 시간 단위 뒤에는 P+VjP + V_j, 두 시간 단위 뒤에는 P+2VjP + 2V_j에 있다. 기구는 한 시간 단위 안에서도 일정한 속도로 흘러가고, 좌표가 0이 되는 순간 관제탑에 닿아 곧바로 회수된다. 시간 단위 도중에 0을 지나가도 그 순간 회수된다.

높이를 바꾸는 데는 시간이 걸리지 않지만 에너지가 든다. 기구 한 대를 높이 H이전H_{\text{이전}}에서 높이 H이후H_{\text{이후}}로 옮기면 에너지 ∣H이전−H이후∣|H_{\text{이전}} - H_{\text{이후}}|를 쓴다. 높이는 정수 시각, 즉 시각 0과 매 시간 단위가 끝나는 시각에만 바꿀 수 있고 횟수 제한은 없다. 쓸 수 있는 에너지는 모든 기구가 함께 나누어 쓰는 QQ뿐이고, 다 쓰지 않아도 된다.

에너지를 가장 알맞게 썼을 때 모든 기구를 회수하는 데 걸리는 시간을 구하라.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스의 첫 줄에는 기구의 수 NN, 높이의 개수 MM, 쓸 수 있는 에너지 QQ가 주어진다.

둘째 줄에는 정수 MM개가 주어진다. 이 줄의 jj번째 값(0부터 센다)이 높이 jj의 바람 속도 VjV_j이다.

이어지는 NN개의 줄에는 기구 한 대의 수평 좌표 PiP_i와 높이 HiH_i가 주어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤101 \le N \le 10
  • 1≤M≤101 \le M \le 10
  • −10≤Vj≤10-10 \le V_j \le 10
  • 1≤Q≤101 \le Q \le 10
  • 0≤Hi<M0 \le H_i < M
  • −10≤Pi≤10-10 \le P_i \le 10

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 모든 기구가 시각 yy까지 회수되도록 하는 가장 작은 정수이다. 주어진 에너지로 모든 기구를 회수할 수 없으면 yy 자리에 IMPOSSIBLE을 출력한다.

힌트

첫 번째 예제 케이스에는 기구가 두 대 있고 에너지는 1이다. 가장 좋은 방법은 시작하자마자 에너지 1을 써서 좌표 3, 높이 3에 있는 기구를 높이 2로 내리는 것이다. 높이 2의 바람은 속도가 −2-2라서 이 기구는 좌표 3에서 1로, 다시 1에서 −1-1로 흘러가며 두 번째 시간 단위 도중에 좌표 0을 지난다. 좌표 −2-2, 높이 1에 있는 기구는 속도 1인 바람을 타고 시간 단위 2에 좌표 0에 닿는다. 그래서 두 기구를 모두 회수하는 데 시간 단위 2가 걸린다.