Language: C++

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
 #include <chrono>
 #include <condition_variable>
 #include <forward_list>
 #include <future>
 #include <initializer_list>
 #include <mutex>
 #include <random>
 #include <ratio>
 #include <regex>
 #include <scoped_allocator>
 #include <system_error>
 #include <thread>
 #include <tuple>
 #include <typeindex>
 #include <type_traits>
 #include <unordered_map>
 #include <unordered_set>
 #endif

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(long long n, std::vector<long long> v, std::vector<long long> w, long long q, std::vector<long long> node, std::vector<long long> cost){
    int dep = 1;
    for(; (1 << dep) < n; ++dep);
    int ma = *max_element(cost.begin(), cost.end()) + 1;
    for(int i = 0; i < q; ++i)
        --node[i];
    if(dep < 10){
        vector<map<int,int>> res(n);
        for(int i = 0; i < n; ++i){
            map<int,int> t;
            t[0] = 0;
            for(int j = i;; j = ((j + 1) >> 1) - 1){
                map<int,int> nex = t;
                for(auto& elm : t)
                    if(elm.first + w[j] <= ma)
                        chmax(nex[elm.first + w[j]], int(elm.second + v[j]));
                int rui = 0;
                for(auto& elm : nex){
                    chmax(rui, elm.second);
                    chmax(elm.second, rui);
                }
                t = move(nex);
                if(!j)
                    break;
            }
            res[i] = move(t);
        }
        for(int i = 0; i < q; ++i){
            auto iter = prev(res[node[i]].upper_bound(cost[i]));
            printf("%d\n", iter->second);
        }
    }
    else{

        vector<vector<int>> query(n);
        vector<int> qans(n, -1);
        for(int i = 0; i < q; ++i)
            query[node[i]].emplace_back(i);

        int border = (1 << (dep / 2)) - 1;
        vector<map<int, int>> res(n);
        auto solve = [&](int i){
            if(node[i] < border){
                auto iter = prev(res[node[i]].upper_bound(cost[i]));
                return iter->second;
            }
            else{
                int j = node[i];
                for(;; j = ((j + 1) >> 1) - 1)
                    if(j < border)
                        break;
                auto& res1 = res[node[i]];
                auto& res2 = res[j];
                int ans = 0;
                for(auto& elm : res1){
                    if(elm.first > cost[i])
                        continue;
                    auto iter = prev(res2.upper_bound(cost[i] - elm.first));
                    chmax(ans, iter->second + elm.second);
                }
                return ans;
            }
        };

        vector<int> cnt(n, 0);
        for(int i = 0; i < n; ++i){
            res[i][0] = 0;
            res[i][w[i]] = v[i];
            int j = ((i + 1) >> 1) - 1;
            if(!(!i || (i >= border && j < border))){
                ++cnt[j];
                res[i] = res[j];
                for(auto& elm : res[j])
                    if(elm.first + w[j] <= ma)
                        chmax(res[i][elm.first + w[i]], int(elm.second + v[i]));
                int rui = 0;
                for(auto& elm : res[i]){
                    chmax(rui, elm.second);
                    elm.second = rui;
                }
                if(j >= border && cnt[j] == 2)
                    map<int,int>().swap(res[j]);
            }
            for(auto idx : query[i]){
                qans[idx] = solve(idx);
            }
        }
        for(int i = 0; i < q; ++i){
            assert(qans[i] != -1);
            printf("%d\n", qans[i]);
        }
    }
}


signed main(){

    /*
    i64 n = (1 << 18);
    i64 q = 1e5;
    vector<i64> v(n, 0);
    vector<i64> w(n, 0);
    for(i64 i = 0; i < n; ++i){
        v[i] = rand() % 100000;
        w[i] = rand() % 1000;
    }
    vector<i64> node(n), cost(n);
    for(i64 i = 0; i < q; ++i){
        node[i] = (rand() % n) + 1;
        cost[i] = rand() % 99999 + 1;
    }
    solve(n, v, w, q, node, cost);
    */

    long long N;
    scanf("%lld",&N);
    std::vector<long long> V(N);
    std::vector<long long> W(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&V[i]);
        scanf("%lld",&W[i]);
    }
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> v(Q);
    std::vector<long long> L(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&v[i]);
        scanf("%lld",&L[i]);
    }
    solve(N, std::move(V), std::move(W), Q, std::move(v), std::move(L));
    return 0;
}


Compiler output:
In file included from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/istream:40,
                 from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from a.cc:26:
/usr/include/c++/14/bits/allocator.h: In destructor 'std::_Vector_base<std::map<int, int>, std::allocator<std::map<int, int> > >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/14/bits/allocator.h:182:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::map<int, int>]': target specific option mismatch
  182 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from a.cc:44:
/usr/include/c++/14/bits/stl_vector.h:132:14: note: called from here
  132 |       struct _Vector_impl
      |              ^~~~~~~~~~~~