가우스

어린 카를 프리드리히 가우스가 수업 시간에 가만히 있지 않자, 선생님은 그를 붙잡아 둘 과제를 하나 만들었다.

선생님은 양의 정수 수열 $F(1), F(2), \ldots, F(K)$를 정하고, $t > K$인 모든 $t$에 대해 $F(t) = 0$으로 둔다. 행운의 수 집합도 함께 정한다. $X$가 행운의 수이면 그 가격을 $C(X)$로 쓴다.

처음에 칠판에는 양의 정수 $A$가 적혀 있다. 가우스는 한 번의 이동마다 다음 둘 중 하나를 한다.

• 칠판에 적힌 수가 $N$일 때, $N$의 약수 중 $N$보다 작은 $M$을 골라 $N$을 지우고 $M$을 적는다. 이 이동의 가격은 $F(d(N/M))$이다. 여기서 $d(x)$는 $x$ 자신을 포함한 $x$의 약수 개수다.
• 칠판에 적힌 수 $N$이 행운의 수이면 $N$을 그대로 둔다. 이 이동의 가격은 $C(N)$이다.

가우스는 정확히 $L$번 이동해야 하고, 마지막 이동을 마친 뒤 칠판에는 $B$가 적혀 있어야 한다. 이렇게 이동하는 방법의 최소 가격을 $G(A, B, L)$이라 하자. 정확히 $L$번 이동해서는 조건을 만족할 수 없으면 $G(A, B, L) = -1$로 정의한다.

선생님은 가우스에게 질의를 $Q$개 준다. 각 질의는 수 $A$와 $B$를 주며, 그 답은 $G(A, B, L_1) + G(A, B, L_2) + \cdots + G(A, B, L_M)$이다. 수 $L_1, \ldots, L_M$은 모든 질의에서 같다.

첫째 줄에 정수 $K$가 주어진다 ($1 \le K \le 10000$).
둘째 줄에 정수 $F(1), F(2), \ldots, F(K)$가 주어지며, 각각 1 이상 1000 이하다.
셋째 줄에 정수 $M$이 주어진다 ($1 \le M \le 1000$).
넷째 줄에 정수 $L_1, L_2, \ldots, L_M$이 주어지며, 각각 1 이상 10000 이하다.
다섯째 줄에 행운의 수의 개수 $T$가 주어진다 ($1 \le T \le 50$).
다음 $T$개 줄에는 각각 두 정수 $X$와 $C(X)$가 주어진다. $X$는 행운의 수이고 $C(X)$는 그 가격이다 ($1 \le X \le 10^6$, $1 \le C(X) \le 1000$). 같은 행운의 수는 두 번 나오지 않는다.
그다음 줄에 정수 $Q$가 주어진다 ($1 \le Q \le 50000$).
다음 $Q$개 줄에는 각각 두 정수 $A$와 $B$가 주어진다 ($1 \le A, B \le 10^6$).

$Q$개 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 출력한다.

$K = 4$이고 $F(1) = F(2) = F(3) = F(4) = 1$, 행운의 수는 2와 4로 $C(2) = 5$, $C(4) = 10$, $L_1 = 1$, $L_2 = 2$, 질의는 $A = 4$, $B = 2$인 경우를 보자.

$L_1 = 1$이면 이동이 한 번뿐이므로 4를 2로 바꾸고 $F(d(4/2)) = F(2) = 1$을 낸다. 따라서 $G(4, 2, 1) = 1$이다.

$L_2 = 2$이면 방법이 두 가지다.

• 4를 2로 바꾼 다음, 2가 행운의 수이므로 그대로 둔다. 가격은 $F(d(4/2)) + C(2) = 1 + 5 = 6$이다.
• 4를 그대로 둔 다음, 2로 바꾼다. 가격은 $C(4) + F(d(4/2)) = 10 + 1 = 11$이다.

첫 번째가 더 싸므로 $G(4, 2, 2) = 6$이고, 질의의 답은 $1 + 6 = 7$이다.