#1655. 「USACO 2025.1 Gold」Median Heap

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

Farmer John 有一棵包含 个结点的二叉树，结点编号从 到 （， 为奇数）。对于 ，结点 的父结点为 。每个结点都有一个初始整数值 ，以及将初始值修改为任意其他整数值的代价 （）。

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

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

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

输入的第一行包含 。

以下 行每行包含两个整数 和 。

以下一行包含 。

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

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

输入 #1

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

输出 #1

111
101
101
100
100
100
100
0
11
11
111

样例 1 解释

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

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

• 测试点 ：。
• 测试点 ：。
• 测试点 ：没有额外限制。