题目描述

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

Farmer John 有一棵包含 $N$ 个结点的二叉树，结点编号从 $1$ 到 $N$（$1 \leq N < 2\cdot 10^5$，$N$ 为奇数）。对于 $i>1$，结点 $i$ 的父结点为 $\lfloor i/2\rfloor$。每个结点都有一个初始整数值 $a_i$，以及将初始值修改为任意其他整数值的代价 $c_i$（$0\le a_i,c_i\le 10^9$）。

他被联邦牛务局（Federal Bovine Intermediary，FBI）委托在这棵树中求出一个近似中位数值，并为此设计了一个聪明的算法。

他从最后一个结点 $N$ 开始向前执行。在算法的每一步，如果一个结点不是它和它的两个结点的中位数，他就交换当前结点和值为中位数的子结点的值。在这个算法结束时，结点 $1$（根结点）上的值即为近似中位数。

FBI 同时给 Farmer John 提供了一份包含 $Q$（$1 \leq Q \leq 2\cdot 10^5$）个独立的询问的清单，每一个询问指定一个目标值 $m$（$0\le m\le 10^9$）。对于每一个询问，FJ 首先会修改某些结点的初始值，然后执行近似中位数算法。对于每一个询问，求 FJ 使得算法输出等于 $m$ 所需要的最小总代价。

输入格式

输入的第一行包含 $N$。

以下 $N$ 行每行包含两个整数 $a_i$ 和 $c_i$。

以下一行包含 $Q$。

以下 $Q$ 行每行包含一个目标值 $m$。

输出格式

输出 $Q$ 行，为对于每一个目标值 $m$ 的最小总代价。

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

111
101
101
100
100
100
100
0
11
11
111

提示

样例 1 解释

为了使近似中位数等于 $40$，FJ 可以将结点 3 的值修改为 $60$。这需要花费 $c_3=100$。

为了使近似中位数等于 $45$，FJ 可以将结点 3 的值修改为 $60$，结点 5 的值修改为 $45$。这需要花费 $c_3+c_5=100+1=101$。

• 测试点 $2\sim 4$：$N,Q\le 50$。
• 测试点 $5\sim 7$：$N,Q\le 1000$。
• 测试点 $8\sim 16$：没有额外限制。