#include <bits/stdc++.h>

using namespace std;

const int N = 19, Q = 1e6 + 50;

int n, m, G[N][N], w[N];
int64_t su[1 << N], ans[Q];
vector<pair<int, int64_t>> dp[1 << N][N];
vector<tuple<int, int>> qu[N];

void update(auto &f, const auto &s, int64_t time_inc, int64_t val_inc) {
	vector<pair<int, int64_t>> result;
	int p0 = 0, p1 = 0;
	while (p0 < f.size() || p1 < s.size()) {
		//fprintf(stderr, "p0 = %d, p1 = %d, f.s = %d, s.s = %d\n", p0, p1, f.size(), s.size());
		auto gogo = [&](int t, int64_t v) {
			if (!result.empty()) {
				auto &[f, s] = result.back();
				if (s > v)
					return;
				if (f == t && s < v) {
					result.pop_back();
				}
				while (result.size() > 2) {
					int n = result.size();
					__int128 k1 = result[n - 2].first, v1 = result[n - 2].second;
					__int128 k2 = result[n - 1].first, v2 = result[n - 1].second;
					__int128 k = t, v = v;
					if ((v - v1) * (k2 - k1) > (v2 - v1) * (k - k1)) {
						result.pop_back();
					}
					else break;
				}
			}
			result.emplace_back(t, v);
		};
		auto ins0 = [&]() {
			gogo(f[p0].first, f[p0].second);
			++p0;
		};
		auto ins1 = [&]() {
			if (time_inc + s[p1].first > 1e9) {
				++p1;
				return;
			}
			gogo(s[p1].first + time_inc, s[p1].second + val_inc);
			++p1;
		};
		if (p1 == s.size()) {
			//fprintf(stderr, "case1\n");
			ins0();
		}
		else if (p0 == f.size()) {
			//fprintf(stderr, "case2\n");
			ins1();
		}
		else if (f[p0].first < s[p1].first + time_inc) {
			//fprintf(stderr, "case3\n");
			ins0();
		}
		else {
			//fprintf(stderr, "case4\n");
			
			ins1();
		}
	}
	assert(is_sorted(result.begin(), result.end(), [&](auto a, auto b) {
		return a.first < b.first;
	}));
	//fprintf(stderr, "finally p0 = %d, p1 = %d\n", p0, p1);
	f = result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	memset(G, 0x3f, sizeof G);
	for (int i = 0; i < n; ++i)
		cin >> w[i];
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		--x, --y;
		G[x][y] = min(G[x][y], z);
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int s, t;
		cin >> t >> s;
		qu[s - 1].emplace_back(t, i);
	}
	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 mask = 0; mask < (1 << n); ++mask) {
		for (int i = 0; i < n; ++i) 
			if (mask >> i & 1) {
				su[mask] = su[mask ^ (1 << i)] + w[i];
				break;
			}
	}
	int full = (1 << n) - 1;
	for (int u = 0; u < n; ++u) {
		if (qu[u].empty()) continue;
		//fprintf(stderr, "u = %d\n", u);
		sort(qu[u].begin(), qu[u].end());
		for (int mask = 0; mask < (1 << n); ++mask)
			for (int v = 0; v < n; ++v)
				dp[mask][v].clear();
		dp[1 << u][u] = { {0, 0} };
		for (int mask = (1 << u); mask < (1 << n); ++mask)
			if (mask >> u & 1) {
				for (int x = 0; x < n; ++x)
					if (mask >> x & 1) {
						for (int v = 0; v < n; ++v)
							if (!(mask >> v & 1)) {
								int new_mask = mask | (1 << v);
								update(dp[new_mask][v], dp[mask][x], G[v][x], G[v][x] * su[mask]);
							}
					}
			}
		vector<tuple<int, int, int64_t>> ops;
		for (int mask = (1 << u); mask < (1 << n); ++mask)
			if (mask >> u & 1) {
				for (int v = 0; v < n; ++v) {
					for (auto [t, val] : dp[mask][v]) {
						//fprintf(stderr, "new op (t = %d, mask = %d, val = %d\n", t, mask, val);
						ops.emplace_back(t, mask, val - t * su[mask]);
					}
				}
			}
		sort(ops.begin(), ops.end());
		int p0 = 0;
		vector<pair<int64_t, int64_t>> cand;
		for (auto [t0, id] : qu[u]) {
			int64_t ret = -1e18;
			while (p0 < ops.size() && get<0>(ops[p0]) <= t0) {
				auto [t, mask, val] = ops[p0];
				cand.emplace_back(su[mask], val);
				++p0;
			}
			sort(cand.begin(), cand.end());
			vector<pair<int64_t, int64_t>> new_cand;
			for (int i = (int)(cand.size()) - 1; i >= 0; --i) {
				int64_t w = cand[i].second + cand[i].first * t0;
				if (w > ret) {
					new_cand.emplace_back(cand[i]);
					ret = w;
				}
			}
			cand = new_cand;
			/*
			for (auto [t, mask, val] : ops) {
				if (t > t0) break;
				//fprintf(stderr, "query #%d (%d, %d), t = %d, mask = %d, val = %lld\n", id, u, t0, t, mask, val);
				ret = max(ret, val + t0 * su[mask]);
			}*/
			ans[id] = ret;
		}
	}
	for (int i = 0; i < q; ++i)
		cout << ans[i] << '\n';
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:22:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:12:13: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   12 | void update(auto &f, const auto &s, int64_t time_inc, int64_t val_inc) {
      |             ^~~~
answer.code:12:28: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   12 | void update(auto &f, const auto &s, int64_t time_inc, int64_t val_inc) {
      |                            ^~~~
answer.code: In lambda function:
answer.code:19:39: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   19 |                                 auto &[f, s] = result.back();
      |                                       ^
answer.code: In function ‘int main()’:
answer.code:131:51: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  131 |                                         for (auto [t, val] : dp[mask][v]) {
      |                                                   ^
answer.code:140:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  140 |                 for (auto [t0, id] : qu[u]) {
      |                           ^
answer.code:143:38: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  143 |                                 auto [t, mask, val] = ops[p0];
      |                                      ^
/usr/bin/ld: /tmp/ccWdRCzy.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccFN9VLv.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccFN9VLv.o: in function `main':
implementer.cpp:(.text.startup+0x12b): undefined reference to `init(int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x1d0): undefined reference to `inv(int)'
collect2: error: ld returned 1 exit status