Cuộn Cỏ Khô

Farmer John quản lý một cây nhị phân có $N$ nút (lẻ). Nút $i$ có cha là $\lfloor i/2\rfloor$. Mỗi nút $i$ có giá trị ban đầu $a_i$ và chi phí thay đổi $c_i$.

Thuật toán xấp xỉ trung vị hoạt động từ nút $N$ đến nút $1$: tại mỗi bước, nếu giá trị nút hiện tại không phải trung vị của nó và hai con, FJ hoán đổi giá trị nút hiện tại với con có giá trị là trung vị. Giá trị cuối cùng tại nút 1 là kết quả xấp xỉ.

FJ có thể thay đổi giá trị của nút $i$ thành bất kỳ giá trị nào với chi phí $c_i$ (hoặc giữ nguyên miễn phí). Cho $Q$ truy vấn, mỗi truy vấn cho giá trị mục tiêu $m$, hãy tìm chi phí tối thiểu để thuật toán trả về $m$.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp: Hai số $a_i$ và $c_i$
• Dòng tiếp: Số nguyên $Q$
• $Q$ dòng tiếp: Mỗi dòng một số $m$

Dữ liệu ra

• $Q$ dòng, mỗi dòng chứa chi phí tối thiểu cho truy vấn tương ứng.

Ràng buộc

• $N,Q\le 2·{10}^5$, $N$ lẻ
• $0\le a_i,c_i,m\le {10}^9$
• Giới hạn thời gian: 4 giây

Ví dụ