중앙값 힙

Farmer John은 $1$부터 $N$까지 번호가 매겨진 노드 $N$개로 이루어진 이진 트리를 가지고 있다 ($1 \leq N < 2\cdot 10^5$, $N$은 홀수). $i>1$인 노드 $i$의 부모는 $\lfloor i/2\rfloor$이다. 각 노드 $i$에는 초기 정수 값 $a_i$와, 그 값을 다른 임의의 정수 값으로 바꾸는 데 드는 비용 $c_i$가 있다 ($0\le a_i,c_i\le 10^9$).

FBI는 Farmer John에게 이 트리에서 근사 중앙값을 찾으라는 과제를 주었고, Farmer John은 이를 위한 알고리즘을 고안했다.

알고리즘은 마지막 노드 $N$에서 시작해 거꾸로 진행한다. 각 단계에서 현재 노드가 자신과 두 자식 중 중앙값이 아니라면, 중앙값이 되는 값을 가진 자식과 현재 노드의 값을 서로 바꾼다. 알고리즘이 끝나면 루트 노드 1의 값이 근사 중앙값이 된다.

FBI는 목표 값 $m$ ($0\le m\le 10^9$)이 지정된 독립적인 질의 $Q$개 ($1 \leq Q \leq 2\cdot 10^5$)도 주었다. 각 질의마다 Farmer John은 먼저 일부 노드의 초기 값을 바꾸고, 그다음 알고리즘을 실행한다. 각 질의에 대해, 알고리즘의 출력이 $m$이 되도록 만드는 최소 총비용을 구하라.

첫 줄에 $N$이 주어진다.

다음 $N$개 줄에는 각각 두 정수 $a_i$와 $c_i$가 주어진다.

다음 줄에는 $Q$가 주어진다.

다음 $Q$개 줄에는 각각 목표 값 $m$이 주어진다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 목표 값 $m$에 대한 최소 총비용을 출력한다.