**Замечание: время на тест для этой задачи 4 сек, в два раза большеЮ чем по умолчанию.**
У Фермера Джона есть двоичное дерево с \(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\)).
ФД должен найти апроксимацию медианы на этом дереве и разработать умный
алгоритм, который это сделает.
Он начинает с последней вершины \(N\) и обрабатывает дерево в обратном порядке.
На каждом шаге алгоритма если вершина не медианная из и имеет двух потомков,
ФД обменивает значения в текущей вершине и потомке, который будет медианой.
В конце этого алгоритма значение в вершине \(1\) и есть медианная аппроксимация.
Также у ФД есть список из \(Q\) \((1 \leq Q \leq 2\cdot 10^5)\) независимых запросов,
которые указывают целевое значение \(m\) (\(0\le m\le 10^9\)). Для каждого запроса
ФД сначала изменяет некоторые начальные значения в вершинах, и затем выполняет
вышеописанный алгоритм медианной аппроксимации. Для каждого запроса определите
минимальную возможную суммарную стоимость, чтобы этот алгоритм давал результат \(m\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Каждая из следующих \(N\) строк содержит два целых числа \(a_i\) и \(c_i\).
Следующая строка содержит \(Q\).
Каждая из следующих \(Q\) содержит целевое значение \(m\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(Q\) строк, минимально возможную стоимость, обеспечивающую ответ \(m\)
как результат работы описанного алгоритма.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|