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

long long K[M],dp[M][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(long long i=0;i<n;i++) cin>>v[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]+=v[i];
	}
	for(long long mac=0;mac<(1<<n);mac++)
		for(long long i=0;i<n;i++)
			dp[mac][i]=INF;
	for(int 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;
			cout<<mac<<" "<<i<<": "<<dp[mac][i]<<'\n';
			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;
	while(q--){
		long long x,u; cin>>x>>u; u--;
		long long ans=0;
		for(long long mac=0;mac<(1<<n);mac++){
			ans=max(ans,K[mac]*x-dp[mac][u]);
		}
		cout<<ans<<'\n';
	}
}