Description

You are given $K$ integers $F(1), F(2), ..., F(K)$, and define $F(i)=0$ for $i>K$. You are also given $T$ lucky integers $X_i$ and their prices $C(X_i)$, and $M$ integers $L_1, L_2, ..., L_M$.

At the beginning, there is an integer $A$ on the blackboard. You can perform the following two operations:

• Let the current number on the blackboard be $N$. You may write down any divisor $M$ of $N$ that is smaller than $N$, paying $F(d(N \div M))$. Here $d(N \div M)$ denotes the number of divisors of the positive integer $N \div M$ (including $N/M$).

• If $N$ is a lucky integer, you may keep $N$ on the blackboard, paying $C(N)$.

Define $G(A,B,L)$ as the minimum cost to start from $A$, perform $L$ operations, and finally leave $B$ on the blackboard. Given $A$ and $B$, compute $G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)$.

Input Format

The first line contains a positive integer $K$.

The second line contains $K$ positive integers $F(1), F(2), ..., F(K)$.

The third line contains a positive integer $M$.

The fourth line contains $M$ positive integers $L_1, L_2, ..., L_M$.

The fifth line contains a positive integer $T$.

The next $T$ lines each contain two positive integers $X_i$ and $C(X_i)$, indicating that $X_i$ is a lucky number and its price is $C(X_i)$.

The $(T+5)$-th line contains a positive integer $Q$, the number of queries.

The next $Q$ lines each contain two positive integers $A$ and $B$.

Output Format

For each query, output $G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)$.

4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2 

7

3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68 

118
-2

3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1 

16
66

Hint

Sample Explanation #1

Since $L_1=1$, replace $4$ with $2$, so the cost is $G(4,2,1)=F(d(2))=1$.

Since $L_2=2$, there are two ways to turn $4$ into $2$:

• Replace $4$ with $2$, and since $2$ is a lucky number, keep $2$ in the second step. The cost is $F(d(4\div 2))+C(2)=1+5=6$.

• Since $4$ is a lucky number, keep $4$ in the first step, then replace $4$ with $2$ in the second step. The cost is $C(4)+F(d(4\div 2))=11+1=12$.

The first plan is cheaper, so choose the first plan.

Therefore, the answer is $G(4,2,1)+G(4,2,2)=1+6=7$.

Constraints

For $100\%$ of the testdata, $1\le K\le 10^4$, $1\le F(i)\le 10^3$, $1\le M\le 10^3$, $1\le L_i\le 10^4$, $1\le T\le 50$, $1\le X_i\le 10^6$, $1\le C(X_i)\le 10^3$, $1\le Q\le 5\times 10^4$, $1\le A,B\le 10^6$.

Notes

The score of this problem follows the original COCI setting, with a full score of $160$.

Translated from COCI2016_2017 CONTEST #6 T6 GAUSS.

Translated by ChatGPT 5