#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 22, MOD = (int)1e9 + 7;
const ll inf = 1e18;

int n, m;
ll d[N][N], c[N], dp[(1 << 19) + 1][20], s[(1 << 19) + 1];
void prec() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                s[i] += c[j];
                if(__builtin_popcount(i) != 1) {
                    dp[i][j] = inf;
                }
            }
        }
    }
}

struct line{
    ll k, b;
    ll get(ll x) {
        return k * x + b;
    }
};
vector<line> st[N];
vector<array<ll, 2>> f[N];


bool check(line x, line y, line z) {
    return (x.b - y.b) * (z.k - y.k) >= (y.b - z.b) * (y.k - x.k);
}
void add(int i, line x) {
    while((int)st[i].size() >= 2 && check(st[i][(int)st[i].size() - 2], st[i].back(), x)) {
        st[i].pop_back();
    }
    st[i].push_back(x);
}
ll get(int i, ll x) {
    ll ret = 0;
    for(auto j:st[i]) {
        ret = max(ret, j.get(x));
    }
    return ret;
}
void test() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> c[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            d[i][j] = inf;
        }
        d[i][i] = 0;
    }
    for(int i = 1; i <= m; i++) {
        int a, b, t;    
        cin >> a >> b >> t;
        a--;
        b--;
        d[a][b] = t;
    }
    prec();
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                for(int k = 0; k < n; k++) {
                    if(!((i >> k) & 1)) {
                        int nv = (i + (1 << k));
                        if(d[j][k] == inf) continue;
                        dp[nv][k] = min(dp[nv][k], dp[i][j] + s[i] * 1ll * d[j][k]);
                    }
                }
            }
        }
    }
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                f[j].push_back({s[i], -dp[i][j]});
            }
        }
    }
    for(int i = 0; i < n; i++) {
        sort(f[i].begin(), f[i].end());
        for(auto [k, b]:f[i]) {
            add(i, {k, b});
        }
    }
    int q;
    cin >> q;

    while(q--) {
        int t, e;
        cin >> t >> e;
        e--;
        ll res = get(e, t);
        // for(int i = 0; i < (1 << n); i++) {
        //     if((i >> e) & 1) {
        //         res = max(res, s[i] * 1ll * t - dp[i][e]);
        //     }
        // }
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}