#include<bits/stdc++.h>
using namespace std;
const long long N=22,M=3e5+5,INF=1e18;
long long n,m,q;
long long a[N],G[N][N];
long long K[M],dp[M][N];
long long X[N],U[N];
long long v[N],vid;


class segtree{
	public:
		struct seg{
			long long k,b;
		}P[N];
		long long id;
		double cal(long long pos,long long x){
			return v[pos]*P[x].k+P[x].b;
		}
		long long f[M*4];
		void modify(long long l,long long r,long long o,long long L,long long R,long long x){
			long long mid=(l+r)>>1;
			if(L<=l && r<=R){
				if(l==r){
					if(cal(l,x)>cal(l,f[o])) f[o]=x;
					return ;
				}
				if(cal(mid,x)>cal(mid,f[o])) swap(f[o],x);
				if(cal(l,x)>cal(l,f[o])) modify(l,mid,o<<1,L,R,x);
				else if(cal(r,x)>cal(r,f[o])) modify(mid+1,r,o<<1|1,L,R,x);
				return ;
			}
			if(L<=mid) modify(l,mid,o<<1,L,R,x);
			if(R>mid) modify(mid+1,r,o<<1|1,L,R,x);
		}
		long long query(long long l,long long r,long long o,long long pos){
			if(l==r) return cal(pos,f[o]);
			long long mid=(l+r)>>1;
			long long tot=cal(pos,f[o]);
			if(pos<=mid) tot=max(tot,query(l,mid,o<<1,pos));
			else tot=max(tot,query(mid+1,r,o<<1|1,pos));
			return tot;
		}
}F[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(long long i=0;i<n;i++) cin>>a[i];
	
	for(long long i=0;i<n;i++)
		for(long long j=0;j<n;j++)
			if(i!=j) G[i][j]=INF;
	for(long long i=1;i<=m;i++){
		long long u,v,w; cin>>u>>v>>w; u--,v--;
		G[u][v]=w;
	}
	for(long long k=0;k<n;k++)
		for(long long i=0;i<n;i++)
			for(long long j=0;j<n;j++)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
	
	for(long long mac=0;mac<(1<<n);mac++){
		for(long long i=0;i<n;i++)
			if(mac>>i & 1) K[mac]+=a[i];
	}
	for(long long mac=0;mac<(1<<n);mac++)
		for(long long i=0;i<n;i++)
			dp[mac][i]=INF;
	for(long long i=0;i<n;i++) dp[1<<i][i]=0;
	
	for(long long mac=0;mac<(1<<n);mac++){
		for(long long i=0;i<n;i++){
			if(!(mac>>i & 1) || dp[mac][i]==INF) continue;
			for(long long j=0;j<n;j++){
				if((mac>>j & 1) || G[i][j]==INF) continue;
				long long nmac=mac | (1<<j);
				dp[nmac][j]=min(dp[nmac][j],dp[mac][i]+G[i][j]*K[mac]);
			}
		}
	}
	
	cin>>q;
	for(long long i=1;i<=q;i++){
		cin>>X[i]>>U[i]; U[i]--;
		v[i]=X[i];
	}
	sort(v+1,v+q+1);
	vid=unique(v+1,v+q+1)-v-1;
	for(long long i=1;i<=q;i++)
		X[i]=lower_bound(v+1,v+vid+1,X[i])-v;
	
	for(long long i=0;i<n;i++){
		for(long long mac=0;mac<(1<<n);mac++){
			if(dp[mac][i]<INF){
				F[i].P[++F[i].id]={K[mac],-dp[mac][i]};
				F[i].modify(1,vid,1,1,vid,F[i].id);
			}
		}
	}
	
	for(long long i=1;i<=q;i++){
		long long x=X[i],u=U[i];
		long long ans=F[u].query(1,vid,1,x);
		cout<<ans<<'\n';
	}
}