#ifndef LOCAL #pragma GCC Optimize("O3,Ofast,unroll-loops") #pragma GCC Target("bmi,bmi2,avx,avx2") #endif #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define int ll #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin() (x).rend() #ifndef LOCAL #define endl "\n" #endif mt19937 rnd(11); struct Node { Node *l, *r; int mn, mx; Node() { l = nullptr; r = nullptr; mn = -1e18; mx = -1e18; } }; void updateMx(Node *root, int l, int r, int ql, int qr, int x) { if (root->mn >= x || l >= qr || r <= ql) { return; } if (ql <= l && r <= qr && root->mx <= x) { root->mx = x; root->mn = x; } else { int m = (l + r) / 2; if (root->l == nullptr) { root->l = new Node(); root->r = new Node(); } if (root->mn == root->mx) { root->l->mn = root->mn; root->r->mn = root->mn; root->l->mx = root->mn; root->r->mx = root->mn; } updateMx(root->l, l, m, ql, qr, x); updateMx(root->r, m, r, ql, qr, x); root->mn = min(root->l->mn, root->r->mn); root->mx = max(root->l->mx, root->r->mx); } } int get(Node *root, int l, int r, int ql, int qr) { if (l >= qr || r <= ql || root->mn > root->mx) { return -1e18; } if (root->mx <= root->mn) { return root->mx; } int m = (l + r) / 2; return max(get(root->l, l, m, ql, qr), get(root->r, m, r, ql, qr)); } void solve() { int n, q; int d, a, b; cin >> n >> q; cin >> d >> a >> b; b = min(b, a * d); int lst = 0; vector<pii> seg; for (int i = 0; i < n; ++i) { int l, r; cin >> l >> r; ++r; seg.pb(mp(lst, l)); lst = r; } seg.pb(mp(lst, ((int)1e12) + 1)); vector<int> ans(q, -1); vector<pii> quests(q); for (int i = 0; i < q; ++i) { int x; cin >> x; quests[i]= mp(x, i); } sort(all(quests)); vector<Node*> S(seg.size()); int ind = 0; int indS = 0; auto go = [&](Node *a, int la, int ra, int i, auto &&self) -> void { if (a->mn > a->mx) { return; } if (a->mn == a->mx) { updateMx(S[i], seg[i].f, seg[i].s, la + d, seg[i].s, a->mx + 1); } else { int m = (la + ra) / 2; self(a->l, la, m, i, self); self(a->r, m, ra, i, self); } }; auto reset = [&](Node *root, int i, int cnt, int l, int r, auto &&self) -> void { if (l >= seg[i].f + d) { return; } if (root->mn > root->mx) { return; } if (root->mn == root->mx) { updateMx(S[i], seg[i].f, seg[i].s, l + cnt * d, seg[i].s, root->mx + cnt); updateMx(S[i], seg[i].f, seg[i].s, l + (cnt - 1) * d, seg[i].s, root->mx + cnt - 1); if (cnt >= 2) { updateMx(S[i], seg[i].f, seg[i].s, l + (cnt - 2) * d, seg[i].s, root->mx + cnt - 2); } } else { int m = (l + r) / 2; self(root->l, i, cnt, l, m, self); self(root->r, i, cnt, m, r, self); } }; for (int i = 0; i < seg.size(); ++i) { S[i] = new Node(); auto x = seg[i]; while (ind < quests.size() && quests[ind].f < x.f) { ++ind; } int l = x.f, r = x.s; if (x.s - x.f > d) { r = l + d; } if (l == 0) { updateMx(S[i], seg[i].f, seg[i].s, 0, seg[i].s, 0); } while (indS < i && seg[indS].s + d <= l) { ++indS; } while (indS < i && seg[indS].s + d <= r) { go(S[indS], seg[indS].f, seg[indS].s, i, go); ++indS; } int indWs = indS; while (indWs < i && seg[indWs].f + d <= r) { go(S[indWs], seg[indWs].f, seg[indWs].s, i, go); ++indWs; } while (ind < quests.size() && quests[ind].f < x.s) { int cnt = (quests[ind].f - x.f) / d; int p = get(S[i], seg[i].f, seg[i].s, seg[i].f, quests[ind].f - cnt * d + 1); p += cnt; if (cnt) { int q = get(S[i], seg[i].f, seg[i].s, seg[i].f, quests[ind].f - (cnt - 1) * d + 1); p = max(p, q + cnt - 1); } if (p >= 0) { ans[quests[ind].s] = (quests[ind].f - p * d) * a + p * b; } ++ind; } if (r != x.s) { int cnt = (x.s - x.f) / d; reset(S[i], i, cnt, x.f, x.s, reset); } // cout << l << " : " << r << endl; // for (int j = l; j < r; ++j) { // cout << get(S[i], seg[i].f, seg[i].s, j, j + 1) << ' '; // } // cout << endl; } for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << endl; } } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(0); #endif int t = 1; // cin >> t; while (t--) { solve(); } }