Gauss

Young Carl Friedrich Gauss would not sit still in class, so his teacher invented a task to keep him busy.

The teacher fixes a sequence of positive integers $F(1), F(2), \ldots, F(K)$ and sets $F(t) = 0$ for every $t > K$. She also fixes a set of lucky numbers. If $X$ is a lucky number, its price is $C(X)$.

At the start a positive integer $A$ is written on the board. In each move Carl does exactly one of the following.

• The number on the board is $N$. He erases it and writes a divisor $M$ of $N$ with $M < N$. The price of this move is $F(d(N/M))$, where $d(x)$ is the number of divisors of $x$, counting $x$ itself.
• The number on the board is $N$ and $N$ is a lucky number. He leaves $N$ on the board. The price of this move is $C(N)$.

Carl must make exactly $L$ moves, and after the last one the number $B$ must be on the board. Let $G(A, B, L)$ be the smallest total price of such a sequence of moves. If no sequence of exactly $L$ moves works, then $G(A, B, L) = -1$.

The teacher gives Carl $Q$ queries. A query gives the numbers $A$ and $B$, and its answer is $G(A, B, L_1) + G(A, B, L_2) + \cdots + G(A, B, L_M)$. The numbers $L_1, \ldots, L_M$ are the same for every query.

The first line contains an integer $K$ ($1 \le K \le 10000$).
The second line contains $K$ integers $F(1), F(2), \ldots, F(K)$, each at least 1 and at most 1000.
The third line contains an integer $M$ ($1 \le M \le 1000$).
The fourth line contains $M$ integers $L_1, L_2, \ldots, L_M$, each at least 1 and at most 10000.
The fifth line contains an integer $T$, the number of lucky numbers ($1 \le T \le 50$).
Each of the next $T$ lines contains two integers $X$ and $C(X)$, meaning that $X$ is a lucky number with price $C(X)$ ($1 \le X \le 10^6$, $1 \le C(X) \le 1000$). No lucky number appears twice.
The next line contains an integer $Q$ ($1 \le Q \le 50000$).
Each of the next $Q$ lines contains two integers $A$ and $B$ ($1 \le A, B \le 10^6$).

Print $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

Take $K = 4$ with $F(1) = F(2) = F(3) = F(4) = 1$, the two lucky numbers 2 and 4 with $C(2) = 5$ and $C(4) = 10$, the values $L_1 = 1$ and $L_2 = 2$, and the query $A = 4$, $B = 2$.

For $L_1 = 1$ Carl has a single move, so he replaces 4 by 2 and pays $F(d(4/2)) = F(2) = 1$. Therefore $G(4, 2, 1) = 1$.

For $L_2 = 2$ he has two options.

• Replace 4 by 2, then leave 2 on the board because 2 is lucky. The price is $F(d(4/2)) + C(2) = 1 + 5 = 6$.
• Leave 4 on the board, then replace it by 2. The price is $C(4) + F(d(4/2)) = 10 + 1 = 11$.

The first option is cheaper, so $G(4, 2, 2) = 6$ and the answer to the query is $1 + 6 = 7$.