E. Red-Black Pepper.cpp

#include <bits/stdc++.h>

using namespace std;

int n, m, X, Y, A, B;

long long int val, x, y;

void gcd(int a, int b){
    bool tmp = a < b;
    pair <int, int> r = {max(a, b), min(a, b)}, s = {1, 0}, t = {0, 1};

    while(r.second){
        int q = r.first / r.second;
        r.first -= r.second * q;
        s.first -= s.second * q;
        t.first -= t.second * q;
        swap(r.first, r.second);
        swap(s.first, s.second);
        swap(t.first, t.second);
    }

    val = r.first, x = s.first, y = t.first;
    if(tmp) swap(x, y);
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> n;
    vector <int> v;
    vector <long long int> sum;
    long long int ans = 0;
    for(int i = 0; i < n; i++){
        cin >> A >> B;
        ans += A;
        v.push_back(B - A);
    }

    sort(v.begin(), v.end(), greater <int> ());
    sum.push_back(0);
    for(int i : v) sum.push_back(sum.back() + i);

    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> X >> Y;
        gcd(X, Y);

        if(n % val){
            cout << "-1\n";
            continue;
        }

        x *= (n / val), y *= (n / val);

        long long int addX = Y / val, addY = X / val;
        if(x < 0) x += addX * (1 << 30), y -= addY * (1 << 30);

        for(long long int tmp = (1 << 30); tmp; tmp >>= 1){
            if(x - addX * tmp >= 0) x -= addX * tmp, y += addY * tmp;
        }

        if(y < 0){
            cout << "-1\n";
            continue;
        }

        long long int lim = 0;
        for(long long int tmp = 30; tmp >= 0; tmp--){
            if(y - addY * (lim + (1 << tmp)) >= 0) lim += 1 << tmp;
        }

        x += addX * lim, y -= addY * lim;

        long long int lo = 0, hi = lim;
        while(lo < hi){
             long long int mid = (lo + hi + 1) >> 1;
            if(v[Y * (y + addY * mid) - 1] < 0) hi = mid - 1;
            else lo = mid;
        }

        y += addY * lo;
        long long int ans2 = sum[y * Y];
        y += addY;
        if(y * Y <= n) ans2 = max(ans2, sum[y * Y]);

        cout << (ans + ans2) << "\n";
    }
}