题目描述

给出 $K$ 个整数 $F(1),F(2),...,F(K)$，并定义 $i>K$ 的 $F(i)=0$；又给出 $T$ 个幸运整数 $X_i$ 和它的价格 $C(X_i)$，$M$ 个整数 $L_1,L_2,...,L_M$。

一开始黑板上有一个整数 $A$，可以进行如下的两种操作：

• 令当前黑板上的数是 $N$，则可以写下 $N$ 的因数中任意一个小于 $N$ 的因数 $M$，花费 $F(d(N\div M))$。其中 $d(N\div M)$ 表示正整数 $N\div M$ 的因数个数（包括 $N/M$）。

• 如果 $N$ 是一个幸运整数，可以将 $N$ 留在黑板上，花费 $C(N)$。

定义 $G(A,B,L)$ 为以 $A$ 为起始的数，进行了 $L$ 次操作，最终留下 $B$ 的最小花费，请你根据给定的 $A$ 和 $B$，求出 $G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)$。

输入格式

第一行，一个正整数 $K$；

第二行，$K$ 个正整数 $F(1),F(2),...,F(K)$；

第三行，一个正整数 $M$；

第四行，$M$ 个正整数 $L_1,L_2,...,L_M$；

第五行，一个正整数 $T$；

接下来 $T$ 行，每行两个正整数 $X_i$ 和 $C(X_i)$，代表 $X_i$ 是一个幸运数且它的价格为 $C(X_i)$；

第 $T+5$ 行，一个正整数 $Q$，表示询问的个数；

接下来 $Q$ 行，每行两个正整数 $A$ 和 $B$。

输出格式

对于输入的每个询问，输出 $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

提示

【样例解释 #1】

因为 $L_1=1$，所以将 $4$ 替换成 $2$，花费 $G(4,2,1)=F(d(2))=1$；

因为 $L_2=2$，所以有两种方法将 $4$ 变成 $2$：

• 将 $4$ 替换成 $2$，又因为 $2$ 是幸运数字，所以第二轮留下 $2$。花费 $F(d(4\div 2))+C(2)=1+5=6$；

• 因为 $4$ 是幸运数字，所以第一轮留下 $4$，第二轮将 $4$ 替换成 $2$。花费 $C(4)+F(d(4\div 2))=11+1=12$。

第一种方案花费更少，所以选择第一种方案。

所以答案是 $G(4,2,1)+G(4,2,2)=1+6=7$。

【数据范围】

对于 $100\%$ 的数据，$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$。

【说明】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 COCI2016_2017 CONTEST #6 T6 GAUSS