{"problem":{"name":"Knapsack Queries on a tree","description":{"content":"We have a rooted binary tree with $N$ vertices, where the vertices are numbered $1$ to $N$. Vertex $1$ is the root, and the parent of Vertex $i$ ($i \\geq 2$) is Vertex $\\left[ \\frac{i}{2} \\right]$. Ea","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"tokiomarine2020_d"},"statements":[{"statement_type":"Markdown","content":"We have a rooted binary tree with $N$ vertices, where the vertices are numbered $1$ to $N$. Vertex $1$ is the root, and the parent of Vertex $i$ ($i \\geq 2$) is Vertex $\\left[ \\frac{i}{2} \\right]$.\nEach vertex has one item in it. The item in Vertex $i$ has a value of $V_i$ and a weight of $W_i$. Now, process the following query $Q$ times:\n\n*   Given are a vertex $v$ of the tree and a positive integer $L$. Let us choose some (possibly none) of the items in $v$ and the ancestors of $v$ so that their total weight is at most $L$. Find the maximum possible total value of the chosen items.\n\nHere, Vertex $u$ is said to be an ancestor of Vertex $v$ when $u$ is an indirect parent of $v$, that is, there exists a sequence of vertices $w_1,w_2,\\ldots,w_k$ ($k\\geq 2$) where $w_1=v$, $w_k=u$, and $w_{i+1}$ is the parent of $w_i$ for each $i$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N < 2^{18}$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq V_i \\leq 10^5$\n*   $1 \\leq W_i \\leq 10^5$\n*   For the values $v$ and $L$ given in each query, $1 \\leq v \\leq N$ and $1 \\leq L \\leq 10^5$.\n\n## Input\n\nLet $v_i$ and $L_i$ be the values $v$ and $L$ given in the $i$\\-th query. Then, Input is given from Standard Input in the following format:\n\n$N$\n$V_1$ $W_1$\n$:$\n$V_N$ $W_N$\n$Q$\n$v_1$ $L_1$\n$:$\n$v_Q$ $L_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"tokiomarine2020_d","tags":[],"sample_group":[["3\n1 2\n2 3\n3 4\n3\n1 1\n2 5\n3 5","0\n3\n3\n\nIn the first query, we are given only one choice: the item with $(V, W)=(1,2)$. Since $L = 1$, we cannot actually choose it, so our response should be $0$.\nIn the second query, we are given two choices: the items with $(V, W)=(1,2)$ and $(V, W)=(2,3)$. Since $L = 5$, we can choose both of them, so our response should be $3$."],["15\n123 119\n129 120\n132 112\n126 109\n118 103\n115 109\n102 100\n130 120\n105 105\n132 115\n104 102\n107 107\n127 116\n121 104\n121 115\n8\n8 234\n9 244\n10 226\n11 227\n12 240\n13 237\n14 206\n15 227","256\n255\n250\n247\n255\n259\n223\n253"]],"created_at":"2026-03-03 11:01:13"}}