Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
scop = [] #高低差,min値
scom = []
scomn = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif sa == ms:
        scomn.append([ms,sa])
    else:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]

print("Yes")


### FIXED CODE ###

n = int(input())
scop = [] #高低差,min値
scom = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in s:
        if i == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif not sa == ms:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]

print("Yes")
### BUGGY CODE ###

N, K = map(int, input().split())
AS = list(map(int, input().split()))
FS = list(map(int, input().split()))
AS.sort(); FS.sort(reverse=True)

def isValid(x):
    trains = 0
    for i in range(N):
        num = AS[i] * FS[i]
        while num > x:
            trains += 1
            num -= FS[i]
    return trains <= K

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo) // 2
    if isValid(mid):
        return binarySearch(lo, mid)
    else:
        return binarySearch(mid + 1, hi)
            
print(binarySearch(0, max(AS[i] * FS[i] for i in range(N))))


### FIXED CODE ###

N, K = map(int, input().split())
AS = list(map(int, input().split()))
FS = list(map(int, input().split()))
AS.sort(); FS.sort(reverse=True)

def isValid(x):
    import math
    trains = 0
    for i in range(N):
        num = AS[i] * FS[i]
        if num <= x: continue
        trains += math.ceil((num - x) / FS[i])
    return trains <= K

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo) // 2
    if isValid(mid):
        return binarySearch(lo, mid)
    else:
        return binarySearch(mid + 1, hi)
            
print(binarySearch(0, max(AS[i] * FS[i] for i in range(N))))
### BUGGY CODE ###

def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return tuple(tuple(x) for x in b)

def double_sum(b,p,q):
    y1,x1 = p
    y2,x2 = q
    if y1>y2 or x1>x2:
        return 0
    else:
        return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2

black = [[0]*kk for i in range(kk)]
white = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        black[x][y]+=1
    else:
        white[x][y]+=1

black = tuple(tuple(black[i%kk]*2) for i in range(kk*2))
white = tuple(tuple(white[i%kk]*2) for i in range(kk*2))

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(kk):
    for j in range(kk):
        b = double_sum(B,[i,j],[i+k-1,j+k-1])\
            + double_sum(B,[i+k,j+k],[i+kk-1,j+kk-1])
        w = double_sum(W,[i,j+k],[i+k-1,j+kk-1])\
            + double_sum(W,[i+k,j],[i+kk-1,j+k-1])
        ans = max(ans,b+w)

print(ans)


### FIXED CODE ###

class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2

z = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x) % kk
    y = int(y) % kk
    if c=='W':
        x = (x+k)%kk
    z[x][y]+=1

z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([0,0],[i-1,j-1])\
            + z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([0,j+k],[i-1,kk-1])\
            + z.sum([i+k,0],[kk-1,j-1])\
            + z.sum([i+k,j+k],[kk-1,kk-1])
        ans = max(ans,a,n-a)

print(ans)
### BUGGY CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for s in reversed(S):
        nextdp = [0] * 13
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nextdp[(i * digit + j) % 13] += dp[j]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(i * digit + j) % 13] %= mod
        else:
            k = int(s)
            for j in range(13):
                nextdp[(k * digit + j) % 13] += dp[j]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(k * digit + j) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

### FIXED CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()
### BUGGY CODE ###

# coding: utf-8
import math


def calc():
    n = int(input())

    tops = list(map(int, input().split()))
    middles = list(map(int, input().split()))
    lowers = list(map(int, input().split()))

    middles = sorted(middles, reverse=True)
    lowers = sorted(lowers, reverse=True)    

    counter = 0
    for top in tops:
        for middle in middles:
            if middle <= top:
                break

            for lower in lowers:
                if lower <= middle:
                    break
                
                counter += 1
                
    return counter

count = calc()
print(count)

### FIXED CODE ###

# coding: utf-8
import math
import bisect

def calc():
    n = int(input())
    tops = list(map(int, input().split()))
    middles = list(map(int, input().split()))
    lowers = list(map(int, input().split()))
 
    tops = sorted(tops)
    lowers = sorted(lowers)
 
    counter = 0
 
    for i in range(n):
        # A < B
        top_num = bisect.bisect_left(tops, middles[i])
        
        # B < C
        lower_num = n - bisect.bisect_right(lowers, middles[i])
        
        counter += top_num * lower_num
    
    return counter
 
print(calc())
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))

    res = 0
    for i in range(n):
        A.pop(0)
        A.pop(-1)
        res += A[-1]
        A.pop(-1)

    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    res = 0
    for i in range(n):
        res += A[-(i + 1) * 2]

    print(res)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
X, Y, A, B, C = map(int, input().split())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)

red = p[:X]
green = q[:Y]
ri = 1
gi = 1

while True :
    if not r :
        break
    red_min = min(red[-ri], red[-1])
    green_min = min(green[-gi], green[-1])
    if red_min > green_min :
        if green_min < r[0] :
            green.remove(green_min)
            green.append(r[0])
            gi += 1
            r.pop(0)
        else :
            break
    else :
        if red_min < r[0] :
            red.remove(red_min)
            red.append(r[0])
            ri += 1
            r.pop(0)
        else :
            break

print(sum(red)+sum(green))


### FIXED CODE ###

import sys
input = sys.stdin.readline
X, Y, A, B, C = map(int, input().split())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p.sort(reverse = True)
q.sort(reverse = True)
red = p[:X]
green = q[:Y]
ans = red + green + r
ans.sort(reverse = True)
print(sum(ans[:X+Y]))
### BUGGY CODE ###

# http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]

uf = UnionFind(H * W)
lst = []
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            th = W * i + j
            lst.append(th)
            if i != 0 and S[i - 1][j] == '.':
                uf.union(W * (i - 1) + j, th)
            if i != H - 1 and S[i + 1][j] == '.':
                uf.union(W * (i + 1) + j, th)
            if j != 0 and S[i][j - 1] == '.':
                uf.union(W * (i) + j - 1, th)
            if j != W - 1 and S[i][j + 1] == '.':
                uf.union(W * (i) + j + 1, th)

g = uf.subsetall()


result = 0
for (le, nu) in g:
    count = 0
    for li in lst:
        if le == uf.find(li):
            count += 1
    result += (nu - count) * count

print(result)

### FIXED CODE ###

from collections import deque


H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '#':
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


print(result)
### BUGGY CODE ###

S=input()
N=len(S)

remainder=[0]*2019
s=''
ans=0
for i in range(N-1,-1,-1):
  s=S[i]+s
  T=int(s)
  n=T%2019
  remainder[n]+=1
  if remainder[n]!=1:
    ans+=remainder[n]-1
ans+=remainder[0]
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

A,B = map(int, input().split())

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

c = cf(A, B)
ch = c[1:]
t =[1]
for i in ch:
    d = make_divisors(i)
    d.pop()
    d.pop(0)
    leng = len(set(d)-set(ch))
    if len(d) == leng:
        t.append(i)
ans=len(t)
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())

def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def prime_factor(n):  # nを素因数分解
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

g = gcd(A, B)
f = prime_factor(g)

ans = len(f)
if f[0][0] != 1:
    ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for r in range(n-1,-1,-1):
  m = r
  for l in range(n):
    if l == m and m + 1 < r:
      m += 1
    while True:
      if a[l] + a[m-1] > a[r] and l < m-1:
        m -= 1
      else:
        break
    if l < m < r:
      ans += r - m
      #print(l,m,r)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for r in range(n-1,-1,-1):
  m = r
  for l in range(n):
    if l == m and m + 1 < r:
      m += 1
    else:
      while True:
        if a[l] + a[m-1] > a[r] and l < m-1:
          m -= 1
        else:
          break
    if l < m < r:
      ans += r - m
      #print(l,m,r)
print(ans)
### BUGGY CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

r,c,k=map(int,input().split())
rcv=[list(map(int,input().split())) for i in range(k)]

dp=[[[0]*(4) for i in range(c+1)] for j in range(r+1)]
# for i in range(r+1):
#     dp[i][0][0]=0
# for i in range(c+1):
#     dp[0][i][0]=0

dic={}
for i in range(k):
    r1,c1,v=rcv[i]
    dic[(r1,c1)]=v

for i in range(r):
    for j in range(c):
        dp[i+1][j+1][0]=max(dp[i+1][j+1][0],max(dp[i][j+1]))
        # if i==1 and j==3:
        #     print(dp[i+1][j+1])
        if (i+1,j+1) in dic:
            for k in range(3)[::-1]:
                # if dp[i+1][j][k]!=-1:
                dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k]+dic[(i+1,j+1)],dp[i+1][j][k]+dic[(i+1,j+1)])
        # if i==1 and j==3:
        #     print(dp[i+1][j+1])
        for k in range(4):
            dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i+1][j][k])
print(max(dp[-1][-1]))

### FIXED CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpn[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
    print(max(dpn[-1]))

main()
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    l = path[pos]
    for i in range(len(l)):
        if visited[l[i]] == -1:
            if ans[l[i]] == -1:
                ans[l[i]] = pos + 1
            queue.append(l[i])
print("Yes")
for i in range(1, n):
    print(ans[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    ll = path[pos]
    for l in ll:
        if visited[l] == -1:
            if ans[l] == -1:
                ans[l] = pos + 1
                queue.append(l)
print("Yes")
for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

# aで読む冊数を固定して、bで何冊読めるか考える
# 累積和にしておく、読めるbの冊数は2分探索で求める
# 計算時間はO(N*logM)


# 2分探索、残りの時間を超えないbの冊数を探索
def binary_search(l, item):
    low = 0
    high = len(l) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = l[mid]
        if guess == item:
            return mid
        elif guess > item:
            high = mid - 1 
        else:
            # elseは guess < item の場合なので、l[mid] == l[-1] は　bが全部読めることを示している
            # l[mid+1] > item ならば l[mid] < item（時間） < l[mid+1] となっている、mid冊は読めるけど、mid+1冊を読む時間はないことを示している
            if l[mid] == l[-1] or l[mid+1] > item:
                return mid
            else:
                low = mid + 1


import itertools

n, m, k = map(int, (input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.insert(0, 0)
b.insert(0, 0)

# aとbの累積和を計算
# accumulateオブジェクトをリストに変換
a_cumsum = list(itertools.accumulate(a))
b_cumsum = list(itertools.accumulate(b))



# 読める本の冊数を記録しておくリスト
books = []

# aの冊数を0冊~最大までそれぞれ固定して、bの冊数を求める
for minute in a_cumsum:
    minutes = 0
    numbers = 0
    
    minutes += minute
    
    if minutes <= k:

        # aの冊数を計算
        numbers += a_cumsum.index(minute)

        # 残り時間
        rest_minutes = k - minutes
        
        # bの冊数を計算
        b_books = binary_search(b_cumsum, rest_minutes)
        numbers += int(b_books)
    
    books.append(numbers)

print(max(books))

### FIXED CODE ###

# aで読む冊数を固定して、bで何冊読めるか考える
# 累積和にしておく、読めるbの冊数は2分探索で求める
# 計算時間はO(N*logM)


import itertools
import bisect

n, m, k = map(int, (input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.insert(0, 0)
b.insert(0, 0)

# aとbの累積和を計算
# accumulateオブジェクトをリストに変換
a_cumsum = list(itertools.accumulate(a))
b_cumsum = list(itertools.accumulate(b))


# 読める本の冊数を記録しておくリスト
books = []


# aの冊数を0冊~最大までそれぞれ固定して、bの冊数を求める
for i in range(len(a_cumsum)):
    minutes = 0
    numbers = 0

    a_minutes = a_cumsum[i]  
    minutes += a_minutes
    
    if minutes <= k:

        # aの冊数を計算
        numbers += i

        # 残り時間
        rest_minutes = k - a_minutes
        
        # bの冊数を計算
        if b_cumsum[-1] == rest_minutes:
            b_books = len(b_cumsum) - 1
        else:
            # bisect.bisect_rightは、リストのどこに数値を入れ込めるかのインデックスを返す（右の）
            b_books = bisect.bisect_right(b_cumsum, rest_minutes)
            b_books -= 1
    
        numbers += b_books
    
    books.append(numbers)

print(max(books))
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    MX = 10**5
    dp1 = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        for j in range(MX + 1):
            dp1[i][j] = dp1[i >> 1][j]
            if j >= w:
                dp1[i][j] = max(dp1[i][j], dp1[i >> 1][j - w] + v)
    for v, L in vL:
        if v < H:
            print(dp1[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    value += items[node - 1][0]
                    weight += items[node - 1][1]
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp1[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

if __name__ == '__main__':
    main()