#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int cost[1000005];
int n, m, l[1005], a[1005], b[1005];
int dp[20][1000005];
void solve(){
memset(dp, 0x3f, sizeof(dp));
dp[0][1] = 0;
for(int i=1; i<20; i++){
for(int j=(1<<(i-1)); j<=500000; j++){
int p = 2;
for(int k=2*j; k<=1000000; k+=j){
dp[i][k] = min(dp[i][k], dp[i-1][j] + cost[p++]);
}
}
}
}
struct cht{
int s, e;
pi a[1005];
void clear(){ s = e = 0;}
void add(pi v){
if(s < e && a[e-1].first == v.first){
if(v.second >= a[e-1].second) return;
else e--;
}
a[e] = v;
while(e - 2 >= s &&
1ll * (a[e-2].second - a[e-1].second) * (a[e].first - a[e-1].first) <=
1ll * (a[e-1].second - a[e].second) * (a[e-1].first - a[e-2].first)){
a[e-1] = a[e];
e--;
}
e++;
}
int query(int x){
if(e == 0) return 2e9;
while(e - 2 >= s && a[e-2].first * x + a[e-2].second <= a[e-1].first * x + a[e-1].second) e--;
return a[e-1].first * x + a[e-1].second;
}
}cht[20];
lint query(int s, int e){
for(int i=0; i<20; i++) cht[i].clear();
for(int i=0; i<m; i++){
if(a[i] % e == 0 && s % a[i] == 0){
for(int j=19; j>=0; j--){
lint av = 2e9;
for(int k=0; k<=j; k++){
lint sum = dp[j-k][a[i] / e] + dp[k][s / a[i]];
av = min(av, sum);
}
if(av < 1e9){
pi w(b[i], (int)av - b[i] * j);
for(int k=j; k<20; k++){
cht[k].add(w);
}
}
}
}
}
lint ret = 0;
for(int i=0; i<n; i++){
int ans = cht[min(l[i], 19)].query(l[i]);
if(l[i] < 20) ans = min(ans, dp[l[i]][s/e]);
if(ans > 1e8) ans = -1;
ret += ans;
}
return ret;
}
int main(){
int t, tmp[10005] = {};
scanf("%d",&t);
for(int i=1; i<=t; i++) scanf("%d",&tmp[i]);
for(int i=1; i<=1000000; i++){
for(int j=i; j<=1000000; j+=i){
cost[j]++;
}
}
for(int i=1; i<=1000000; i++) cost[i] = tmp[cost[i]];
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%d",&l[i]);
sort(l, l+n);
scanf("%d",&m);
vector<pi> v;
for(int i=0; i<m; i++) scanf("%d %d",&a[i],&b[i]);
for(int i=0; i<m; i++) v.push_back(pi(b[i], a[i]));
sort(v.begin(), v.end());
for(int i=0; i<m; i++){
b[i] = v[i].first, a[i] = v[i].second;
}
solve();
int q; scanf("%d",&q);
while(q--){
int a, b;
scanf("%d %d",&a,&b);
if(a % b != 0) printf("%d\n", -n);
else printf("%lld\n", query(a, b));
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxpbnQ7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcGk7CgppbnQgY29zdFsxMDAwMDA1XTsKaW50IG4sIG0sIGxbMTAwNV0sIGFbMTAwNV0sIGJbMTAwNV07CmludCBkcFsyMF1bMTAwMDAwNV07Cgp2b2lkIHNvbHZlKCl7CgltZW1zZXQoZHAsIDB4M2YsIHNpemVvZihkcCkpOwoJZHBbMF1bMV0gPSAwOwoJZm9yKGludCBpPTE7IGk8MjA7IGkrKyl7CgkJZm9yKGludCBqPSgxPDwoaS0xKSk7IGo8PTUwMDAwMDsgaisrKXsKCQkJaW50IHAgPSAyOwoJCQlmb3IoaW50IGs9MipqOyBrPD0xMDAwMDAwOyBrKz1qKXsKCQkJCWRwW2ldW2tdID0gbWluKGRwW2ldW2tdLCBkcFtpLTFdW2pdICsgY29zdFtwKytdKTsKCQkJfQoJCX0KCX0KfQoKc3RydWN0IGNodHsKCWludCBzLCBlOwoJcGkgYVsxMDA1XTsKCXZvaWQgY2xlYXIoKXsgcyA9IGUgPSAwO30KCXZvaWQgYWRkKHBpIHYpewoJCWlmKHMgPCBlICYmIGFbZS0xXS5maXJzdCA9PSB2LmZpcnN0KXsKCQkJaWYodi5zZWNvbmQgPj0gYVtlLTFdLnNlY29uZCkgcmV0dXJuOwoJCQllbHNlIGUtLTsKCQl9CgkJYVtlXSA9IHY7CgkJd2hpbGUoZSAtIDIgPj0gcyAmJiAKCQkJMWxsICogKGFbZS0yXS5zZWNvbmQgLSBhW2UtMV0uc2Vjb25kKSAqIChhW2VdLmZpcnN0IC0gYVtlLTFdLmZpcnN0KSA8PQoJCQkxbGwgKiAoYVtlLTFdLnNlY29uZCAtIGFbZV0uc2Vjb25kKSAqIChhW2UtMV0uZmlyc3QgLSBhW2UtMl0uZmlyc3QpKXsKCQkJYVtlLTFdID0gYVtlXTsKCQkJZS0tOwoJCX0KCQllKys7Cgl9CglpbnQgcXVlcnkoaW50IHgpewoJCWlmKGUgPT0gMCkgcmV0dXJuIDJlOTsKCQl3aGlsZShlIC0gMiA+PSBzICYmIGFbZS0yXS5maXJzdCAqIHggKyBhW2UtMl0uc2Vjb25kIDw9IGFbZS0xXS5maXJzdCAqIHggKyBhW2UtMV0uc2Vjb25kKSBlLS07CgkJcmV0dXJuIGFbZS0xXS5maXJzdCAqIHggKyBhW2UtMV0uc2Vjb25kOwoJfQp9Y2h0WzIwXTsKCmxpbnQgcXVlcnkoaW50IHMsIGludCBlKXsKCWZvcihpbnQgaT0wOyBpPDIwOyBpKyspIGNodFtpXS5jbGVhcigpOwoJZm9yKGludCBpPTA7IGk8bTsgaSsrKXsKCQlpZihhW2ldICUgZSA9PSAwICYmIHMgJSBhW2ldID09IDApewoJCQlmb3IoaW50IGo9MTk7IGo+PTA7IGotLSl7CgkJCQlsaW50IGF2ID0gMmU5OwoJCQkJZm9yKGludCBrPTA7IGs8PWo7IGsrKyl7CgkJCQkJbGludCBzdW0gPSBkcFtqLWtdW2FbaV0gLyBlXSArIGRwW2tdW3MgLyBhW2ldXTsKCQkJCQlhdiA9IG1pbihhdiwgc3VtKTsKCQkJCX0KCQkJCWlmKGF2IDwgMWU5KXsKCQkJCQlwaSB3KGJbaV0sIChpbnQpYXYgLSBiW2ldICogaik7CgkJCQkJZm9yKGludCBrPWo7IGs8MjA7IGsrKyl7CgkJCQkJCWNodFtrXS5hZGQodyk7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJfQoJbGludCByZXQgPSAwOwoJZm9yKGludCBpPTA7IGk8bjsgaSsrKXsKCQlpbnQgYW5zID0gY2h0W21pbihsW2ldLCAxOSldLnF1ZXJ5KGxbaV0pOwoJCWlmKGxbaV0gPCAyMCkgYW5zID0gbWluKGFucywgZHBbbFtpXV1bcy9lXSk7CgkJaWYoYW5zID4gMWU4KSBhbnMgPSAtMTsKCQlyZXQgKz0gYW5zOwoJfQoJcmV0dXJuIHJldDsKfQoKaW50IG1haW4oKXsKCWludCB0LCB0bXBbMTAwMDVdID0ge307CglzY2FuZigiJWQiLCZ0KTsKCWZvcihpbnQgaT0xOyBpPD10OyBpKyspIHNjYW5mKCIlZCIsJnRtcFtpXSk7Cglmb3IoaW50IGk9MTsgaTw9MTAwMDAwMDsgaSsrKXsKCQlmb3IoaW50IGo9aTsgajw9MTAwMDAwMDsgais9aSl7CgkJCWNvc3Rbal0rKzsKCQl9Cgl9Cglmb3IoaW50IGk9MTsgaTw9MTAwMDAwMDsgaSsrKSBjb3N0W2ldID0gdG1wW2Nvc3RbaV1dOwoJc2NhbmYoIiVkIiwmbik7Cglmb3IoaW50IGk9MDsgaTxuOyBpKyspIHNjYW5mKCIlZCIsJmxbaV0pOwoJc29ydChsLCBsK24pOwoJc2NhbmYoIiVkIiwmbSk7Cgl2ZWN0b3I8cGk+IHY7Cglmb3IoaW50IGk9MDsgaTxtOyBpKyspIHNjYW5mKCIlZCAlZCIsJmFbaV0sJmJbaV0pOwoJZm9yKGludCBpPTA7IGk8bTsgaSsrKSB2LnB1c2hfYmFjayhwaShiW2ldLCBhW2ldKSk7Cglzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7Cglmb3IoaW50IGk9MDsgaTxtOyBpKyspewoJCWJbaV0gPSB2W2ldLmZpcnN0LCBhW2ldID0gdltpXS5zZWNvbmQ7Cgl9Cglzb2x2ZSgpOwoJaW50IHE7IHNjYW5mKCIlZCIsJnEpOwoJd2hpbGUocS0tKXsKCQlpbnQgYSwgYjsKCQlzY2FuZigiJWQgJWQiLCZhLCZiKTsKCQlpZihhICUgYiAhPSAwKSBwcmludGYoIiVkXG4iLCAtbik7CgkJZWxzZSBwcmludGYoIiVsbGRcbiIsIHF1ZXJ5KGEsIGIpKTsKCX0KfQo=