题目描述
Problem Description
Given $K$ integers $F(1), F(2), ..., F(K)$, and define $F(i) = 0$ for $i > K$; also given $T$ lucky integers $X_i$ and their prices $C(X_i)$, and $M$ integers $L_1, L_2, ..., L_M$.
Initially, there is an integer $A$ on the blackboard, and you can perform the following two operations:
-
Let the current number on the blackboard be $N$, you can write any divisor $M$ of $N$ that is less than $N$, with a cost of $F(d(N \div M))$. Here, $d(N \div M)$ denotes the number of divisors of the integer $N \div M$ (including $N/M$).
-
If $N$ is a lucky integer, you can keep $N$ on the blackboard with a cost of $C(N)$.
Define $G(A, B, L)$ as the minimum cost to start with $A$, perform $L$ operations, and end up with $B$. You need to calculate $G(A, B, L_1) + G(A, B, L_2) + ... + G(A, B, L_M)$ for given $A$ and $B$.
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 contain two positive integers each, $X_i$ and $C(X_i)$, representing that $X_i$ is a lucky number with a price of $C(X_i)$.
The $T+5$-th line contains a positive integer $Q$, the number of queries.
The next $Q$ lines contain two positive integers each, $A$ and $B$.
Output Format
For each query, output $G(A, B, L_1) + G(A, B, L_2) + ... + G(A, B, L_M)$.
Sample Input and Output
Input Sample #1
4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2
Output Sample #1
7
Input Sample #2
3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68
Output Sample #2
118
-2
Input Sample #3
3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1
Output Sample #3
16
66
Notes
[Sample Explanation #1]
Since $L_1 = 1$, replace $4$ with $2$, costing $G(4, 2, 1) = F(d(2)) = 1$.
Since $L_2 = 2$, there are two ways to transform $4$ into $2$:
-
Replace $4$ with $2$, and since $2$ is a lucky number, keep $2$ in the second round. Cost: $F(d(4 \div 2)) + C(2) = 1 + 5 = 6$.
-
Since $4$ is a lucky number, keep $4$ in the first round, and replace $4$ with $2$ in the second round. Cost: $C(4) + F(d(4 \div 2)) = 11 + 1 = 12$.
The first option is cheaper, so choose the first option.
Thus, the answer is $G(4, 2, 1) + G(4, 2, 2) = 1 + 6 = 7$.
[Data Range]
For $100\%$ of the data, $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]
This problem's score is set according to the original COCI contest, with a full score of $160$.
Translated from COCI2016_2017 CONTEST #6 T6 GAUSS.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分