Language: C++

#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> v(n + 1), w(n + 1);
    rep(i, n) cin >> v[i + 1] >> w[i + 1];

    vector<pair<ll, ll>> x, y[1000];
    vector<ll> a, b;

    y[0].emplace_back(0, 0);
    for(ll i = 1; i * i <= n; i++) {
        x.clear();
        for(auto [p, q] : y[i >> 1]) {
            x.emplace_back(p, q);
            if(p + w[i] <= 100000) x.emplace_back(p + w[i], q + v[i]);
        }
        sort(ALL(x));
        ll mx = -1;
        for(auto p : x)
            if(chmax(mx, p.second)) y[i].push_back(p);
    }

    ll m;
    cin >> m;
    rep(_, m) {
        ll q, l;
        cin >> q >> l;
        if(q * q <= n)
            cout << (upper_bound(ALL(y[q]), make_pair(l, 1 << 30)) - 1)->second
                 << "\n";
        else {
            a.clear();
            b.clear();
            ll N = 0;
            for(; q * q > n; q >>= 1) {
                a.push_back(v[q]);
                b.push_back(w[q]);
                N++;
            }
            ll ret = -1;
            rep(i, 1 << N) {
                ll sumv = 0, sumw = 0;
                rep(j, N) if(i >> j & 1) {
                    sumv += a[j];
                    sumw += b[j];
                }
                if(sumw <= l) {
                    chmax(ret,
                          sumv + (upper_bound(ALL(y[q]),
                                              make_pair(l - sumw, 1 << 30)) -
                                  1)
                                     ->second);
                }
            }
            cout << ret << "\n";
        }
    }

    return 0;
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = const std::pair<long long int, int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >]':
/usr/include/c++/14/bits/stl_algo.h:1993:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, int>; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
 1993 |           if (__comp(__val, __middle))
      |               ~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:2028:32:   required from '_FIter std::upper_bound(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, int>]'
 2028 |       return std::__upper_bound(__first, __last, __val,
      |              ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
 2029 |                                 __gnu_cxx::__ops::__val_less_iter());
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:56:33:   required from here
   56 |             cout << (upper_bound(ALL(y[q]), make_pair(l, 1 << 30)) - 1)->second
      |                      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:98:22: error: no match for 'operator<' (operand types are 'const std::pair<long long int, int>' and 'std::pair<long long int, long long int>')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181:
/usr/include/c++/14/bits/regex.h:1143:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1143 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1143:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1224 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1317 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1391 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1485 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1560 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1660 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   deduced conflicting types for parameter '_T2' ('int' and 'long long int')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |