Printing Press

A publisher has to print $N$ books within $X$ days. Books can normally be printed in parallel, but the publisher puts ordering restrictions on some of them. Volume 2 of a series cannot start printing before volume 1 is published, for instance. There are $M$ restrictions, each given as a pair $(u, v)$, which means that printing of book $v$ can start only after book $u$ is published.

Printing book $i$ takes $A_i$ days and costs $C_i$. With extra resources on the presses, the printing time of book $i$ can be cut by $R_i$ days down to $A_i - R_i$ days, subject to $A_i - R_i \ge B_i$. Every day cut off costs an extra $D_i$.

Days are counted from day 0. If book $i$ starts on day $S_i$, its printing ends on day $S_i + (A_i - R_i) - 1$. A restriction $(u, v)$ means $S_v \ge S_u + (A_u - R_u)$, and every book must satisfy $S_i + (A_i - R_i) \le X$.

The total cost is the sum of the printing costs plus the sum of the shortening costs, $\sum_i C_i + \sum_i D_i R_i$. Find the minimum total cost of printing all $N$ books within $X$ days.

The first line holds the number of test cases $T$. Each test case has the following format.

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$
• The same pair $(u, v)$ is never given twice, and the restrictions contain no cycle.

The distribution of $N$ is as follows. 85% of the test cases have $N \le 30$, three of them have $N = 200$, and the rest have $30 \le N \le 100$.

Print one line per test case. The line starts with Case k: , where $k$ is the test case number counting from 1. Append Impossible if the $N$ books cannot all be printed within $X$ days, otherwise append the minimum total cost.

The figure below shows an example with three books. Book 1 takes 5 days and cannot be shortened. Book 2 and book 3 take 4 days each, and book 3 can start only after book 2 is published. Without extra resources all three books take 8 days. Cutting 2 days from book 2 and 1 day from book 3 finishes everything in 5 days.