인쇄소

출판사가 책 $N$권을 $X$일 안에 모두 인쇄하려 한다. 책은 원래 여러 권을 동시에 찍을 수 있지만, 출판사가 일부 책에 순서 제약을 걸어 두었다. 어떤 시리즈의 2권은 1권이 출간되기 전에는 인쇄를 시작할 수 없는 식이다. 제약은 $M$개이고 각각 $(u, v)$ 꼴로 주어진다. $u$번 책이 출간된 뒤에야 $v$번 책의 인쇄를 시작할 수 있다는 뜻이다.

$i$번 책을 찍는 데는 $A_i$일이 걸리고 인쇄 비용은 $C_i$다. 인쇄기에 자원을 더 넣으면 제작 기간을 $R_i$일 줄여 $A_i - R_i$일 만에 끝낼 수 있다. 단 $A_i - R_i \ge B_i$를 지켜야 하고, 하루를 줄일 때마다 $D_i$의 비용이 더 든다.

일정은 0일차부터 센다. $i$번 책을 $S_i$일차에 시작하면 $S_i + (A_i - R_i) - 1$일차에 인쇄가 끝난다. 제약 $(u, v)$는 $S_v \ge S_u + (A_u - R_u)$를 뜻하고, 모든 책은 $S_i + (A_i - R_i) \le X$를 만족해야 한다.

총비용은 인쇄 비용의 합에 단축 비용의 합을 더한 $\sum_i C_i + \sum_i D_i R_i$다. $N$권을 모두 $X$일 안에 찍을 때의 최소 총비용을 구하라.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스는 다음 형식이다.

N X
A1 A2 ... AN
B1 B2 ... BN
C1 C2 ... CN
D1 D2 ... DN
M
u1 v1
...
uM vM

• $1 \le T \le 300$
• $1 \le N \le 200$, $1 \le X \le 10^7$
• $1 \le A_i \le 10^6$, $1 \le B_i \le A_i$
• $1 \le C_i \le 10^6$, $0 \le D_i \le 100$
• $0 \le M \le N(N-1)/2$, $1 \le u_i, v_i \le N$, $u_i \ne v_i$
• 같은 $(u, v)$ 쌍은 두 번 주어지지 않고, 제약에 순환은 없다.

$N$의 분포는 이렇다. 테스트 케이스의 85%는 $N \le 30$이고, 3개는 $N = 200$이며, 나머지는 $30 \le N \le 100$이다.

각 테스트 케이스마다 한 줄씩 출력한다. 줄은 Case k: 로 시작하고, $k$는 1부터 시작하는 테스트 케이스 번호다. $X$일 안에 $N$권을 다 찍을 수 없으면 뒤에 Impossible을 붙이고, 찍을 수 있으면 최소 총비용을 붙인다.

아래 그림은 책 3권짜리 예다. 1번 책은 5일이 걸리고 단축할 수 없다. 2번 책과 3번 책은 각각 4일이 걸리고 2번이 끝나야 3번을 시작할 수 있다. 자원을 더 넣지 않으면 세 권을 모두 찍는 데 8일이 걸린다. 2번 책을 2일, 3번 책을 1일 줄이면 5일 만에 끝난다.