AT_tokiomarine2020_d Knapsack Queries on a tree

[problemUrl]: https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_d $ N $ 頂点からなる根付き二分木があり、各頂点には $ 1 $ から $ N $ までの番号がついています。 頂点 $ 1 $ が根であり、頂点 $ i $ ($ i\ \geqq\ 2 $) の親は頂点 $ \left[\ \frac{i}{2}\ \right] $ です。 各頂点には $ 1 $ つのアイテムがあります。頂点 $ i $ にあるアイテムの価値は $ V_i $ であり、重さは $ W_i $ です。 そこで、次のクエリに $ Q $ 回答えてください。 - 二分木の頂点 $ v $ 及び正の整数 $ L $ が与えられる。 $ v $ 及び $ v $ の先祖にあるアイテムを、重さの合計が $ L $ 以下となるようにいくつか（$ 0 $ 個でもよい）選ぶ。 このとき、選んだアイテムの価値の総和の最大値を求めよ。 ただし、頂点 $ u $ が頂点 $ v $ の先祖であるとは、頂点 $ u $ が頂点 $ v $ の間接的な親である、つまり、 $ w_1=v $、$ w_k=u $、さらに各 $ i $ について $ w_{i+1} $ が $ w_i $ の親となるような頂点の列 $ w_1,w_2,\ldots,w_k $ ($ k\geqq\ 2 $) が存在することを指します。

$ i $ 回目のクエリで指定される $ v $, $ L $ をそれぞれ $ v_i $, $ L_i $ とする。 このとき、入力は以下の形式で標準入力から与えられる。 > $ N $ $ V_1 $ $ W_1 $ $ : $ $ V_N $ $ W_N $ $ Q $ $ v_1 $ $ L_1 $ $ : $ $ v_Q $ $ L_Q $

$ 1 $ から $ Q $ までの各整数 $ i $ について、 $ i $ 回目のクエリに対する答えを $ i $ 行目に出力せよ。

### 制約 - $ 1\ \leqq\ N\