配点 : $700$ 点

問題文

$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$) が存在することを指します。

制約

• $1 \leqq N < 2^{18}$
• $1 \leqq Q \leqq 10^5$
• $1 \leqq V_i \leqq 10^5$
• $1 \leqq W_i \leqq 10^5$
• 各クエリで指定される $v$, $L$ は $1 \leqq v \leqq N$, $1 \leqq L \leqq 10^5$ を満たす。
• 入力で与えられる値はすべて整数である。

入力

$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$ 行目に出力せよ。

3
1 2
2 3
3 4
3
1 1
2 5
3 5

0
3
3

最初のクエリでは、選ぶことのできるアイテムは $(V,W)=(1,2)$ なるアイテムのみであるので、 $L=1$ より $1$ つもアイテムを選ぶことができません。 したがって、答えは $0$ になります。

一方で $2$ 番目のクエリでは、選ぶことのできるアイテムは $(V,W)=(1,2)$ なるアイテムと $(V,W)=(2,3)$ なるアイテムの $2$ つであり、 $L=5$ より両方を選ぶことができます。 したがって、答えは $3$ になります。

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

256
255
250
247
255
259
223
253