P7790 [COCI 2016/2017 #6] Gauss

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)$.

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$.

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

**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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T6 GAUSS**_. Translated by ChatGPT 5