#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 18;
const int M = 1 << 18;
const int lim = 1e9;

int n, m, q, a[N];
ll g[N][N], f[M][N], h[M];

struct seg
{
	ll k, b;
	seg(ll _k = 0, ll _b = 0) {k = _k, b = _b;}
	ll F(ll x) {return  k * x + b;}
};

int cnt, rt[N], ls[M * 30], rs[M * 30];
seg t[M * 30];

void ins(int &rt, int l, int r, seg s)
{
	if(!rt) rt = ++cnt;
	int mid = (l + r) >> 1;
	if(t[rt].F(mid) < s.F(mid)) swap(t[rt], s);
	if(l == r) return;
	if(t[rt].F(l) < s.F(l)) ins(ls[rt], l, mid, s);
	if(t[rt].F(r) < s.F(r)) ins(rs[rt], mid + 1, r, s);
	return;
}

ll qry(int rt, int l, int r, ll x)
{
	ll res = t[rt].F(x);
	if(l == r) return res;
	int mid = (l + r) >> 1;
	if(x <= mid) res = max(res, qry(ls[rt], l, mid, x));
	else res = max(res, qry(rs[rt], mid + 1, r, x));
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i];

	memset(g, 0x3f, sizeof(g));
	for(int i = 1, u, v, w; i <= m; i++)
		cin >> u >> v >> w, g[u - 1][v - 1] = w;

	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

	for(int S = 1; S < (1 << n); S++)
		h[S] = h[S ^ (S & -S)] + a[__lg(S & -S)];

	memset(f, 0x3f, sizeof(f));
	for(int i = 0; i < n; i++) f[1 << i][i] = 0;
	for(int S = 1; S < (1 << n); S++)
		for(int i = 0; i < n; i++) if(S >> i & 1)
			for(int j = 0; j < n; j++) if(!(S >> j & 1))
				f[S | (1 << j)][j] = min(f[S | (1 << j)][j], f[S][i] + g[i][j] * h[S]);

	for(int i = 0; i < n; i++)
		for(int S = 0; S < (1 << n); S++)
			ins(rt[i], 1, lim, seg(h[S], -f[S][i]));

	cin >> q;
	while(q--)
	{
		int x, y; cin >> x >> y;
		cout << qry(rt[y - 1], 1, lim, x) << '\n';
	}
	return 0;
}