
#include <iostream>
#include <iomanip>
#include <vector>
#include <tuple>
#include <algorithm>
#include <unordered_set>
#include <cmath>

using ull = unsigned long long;
using ll = long long;

#define REP(i, n) for(ll i=0;i<(ll)n;i++)
constexpr bool bitp(ull bits, ull pos) { return bits & (1ULL << pos); }

struct shiki {
    static constexpr ll limit = std::numeric_limits<ll>::max() / 4;
    ll min = 10000000000000000;
    ll max = -10000000000000000;
    ll a = 0;
    shiki(ll _a, ll t) {
        switch (t)
        {
            case 1: a = _a; break;
            case 2: max = _a; break;
            case 3: min = _a; break;
        }
    }
    void gousei(const shiki& sotogawa) {
        if(sotogawa.min < 10000000000000000) min = std::min(min, sotogawa.min - a);
        if(sotogawa.max > -10000000000000000) max = std::max(max, sotogawa.max - a);
        a += sotogawa.a;
    }
    void gousei(ll _a, ll t) {
        switch (t)
        {
            case 1: a += _a; max += _a; min += _a; break;
            case 2: max = std::max(max, _a); min = std::max(min, _a); break;
            case 3: min = std::min(min, _a); max = std::min(max, _a); break;
        }
    }
    ll execute(ll x) {
        return std::min(std::max(x + a, max), min);
    }
    void print() { std::cout << min << " " << max << " " << a << "\n"; }
};

int main() {
    ull N, Q;
    std::cin >> N;
    shiki f(0,0);
    REP(i, N) {
        ll a, t;
        std::cin >> a >> t;
        f.gousei(a, t);
        //f.gousei(shiki(a, t));
        //f.print();
    }
    std::cin >> Q;
    std::vector<ll> x(Q);
    REP(i, Q) std::cin >> x[i];
    REP(i, Q) std::cout << f.execute(x[i]) << "\n";
}

// #pragma GCC target ("avx,avx2")
// #include <bits/extc++.h>
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

#define f first
#define s second

using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
// typedef tree<int, null_type, less<int>, 
// rb_tree_tag, tree_order_statistics_node_update> oset;
//========================================================
const int N = 1e5+5, K = 19, M = 5e4+5, mod = 1e9+7, len = 30, inf = 0x3f3f3f3f;
int n, m;
ll dist[N];

vector<pair<int, pair<ll, ll>>> adj[N];

void dijkstra(int src)
{
	priority_queue<pair<ll, int>> q;

	fill(dist, dist+n, 1e18);

	q.push({0, src});
	dist[src] = 0;

	while(!q.empty())
	{
		auto t = q.top();
		q.pop();

		int u = t.s;
		if(dist[u] != -t.f)
			continue;
		if(u == n-1)
			break;
		for(auto e : adj[u])
		{
			ll v = e.f, c = e.s.f, d = e.s.s;
			auto dis = [&](ll T)
			{
				ll res = c + ll(d / (T + 1)) + T;
				return res;
			};

			ll s = 1ll * sqrt(d) - 1;
			s = max(s, 0LL);
			if(dist[u] > s)
				s = dist[u];
			ll D = min(dis(s), dis(s+1));
			// assert(D > 0);
			if(dist[v] > D)
				dist[v] = D, q.push({-D, v});
		}
	}
	if(dist[n-1] == 1e18)
		dist[n-1] = -1;
}

void run_case()
{
	scanf("%d %d", &n, &m);
	for(int i=0, u, v, c, d; i<m; i++)
	{
		scanf("%d %d %d %d", &u, &v, &c, &d);
		adj[u-1].push_back({v-1, {c, d}});
		adj[v-1].push_back({u-1, {c, d}});
	}

	dijkstra(0);
	printf("%lld\n", dist[n-1]);
}

int main()
{
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("input.txt", "rt", stdin);
    // freopen("output.txt", "wt", stdout);
    int t;
    t = 1;
    // cin >> t;
    while(t--)
        run_case();
}
