Median Heap

Farmer John has a binary tree with $N$ nodes, numbered from $1$ to $N$ ($1 \leq N < 2\cdot 10^5$, and $N$ is odd). For $i>1$, the parent of node $i$ is $\lfloor i/2\rfloor$. Each node has an initial integer value $a_i$ and a cost $c_i$ to change it to any other integer value ($0\le a_i,c_i\le 10^9$).

The Federal Bovine Intermediary (FBI) asked Farmer John to find an approximate median value in this tree. He devised an algorithm for it.

He starts at the last node $N$ and works backward. At each step, if a node would not be the median of itself and its two children, he swaps the node's value with the child value that would be the median. When the algorithm ends, the value at the root (node $1$) is the approximate median.

The FBI also gave him $Q$ independent queries ($1 \leq Q \leq 2\cdot 10^5$), each with a target value $m$ ($0\le m\le 10^9$). For each query, Farmer John first changes some of the initial values, then runs the algorithm. For each query, find the minimum total cost needed to make the algorithm's output equal $m$.

The first line contains $N$.

The next $N$ lines each contain two integers $a_i$ and $c_i$.

The next line contains $Q$.

The next $Q$ lines each contain a target value $m$.

Output $Q$ lines. Each line contains the minimum total cost for the corresponding target value $m$.