Harryxun/stf_run huggingface dataset:
n = int(input())
MOD = 1000000007

ans = 1
x_sardines = []
ver_sardines = []
hor_sardines  = []
zero_sardines  = []

for _ in range(n):
  ai, bi = map(int, input().split())
  if ai == 0 and bi != 0:
    ver_sardines.append((ai, bi))
  elif ai != 0 and bi == 0:
    hor_sardines.append((ai, bi))
  elif ai == 0 and bi == 0:
    zero_sardines.append((ai, bi))
  elif bi / ai > 0:
    x_sardines.append((ai, bi, 1))
  elif bi / ai < 0:
    x_sardines.append((- 1 * bi, ai, -1))

x_sardines.sort(key = lambda x: x[1] / x[0])

pai, pbi, ps = x_sardines[0]
p = 1 if ps == 1 else 0
n = 1 if ps == -1 else 0
for i, (ai, bi, s) in enumerate(x_sardines[1:]):
  if pai * bi - pbi * ai != 0:
    ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
    p = 0
    n = 0
    
  if s == 1:
    p += 1
  elif s == -1:
    n += 1
  pai, pbi, ps = ai, bi, s

ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
  
v = len(ver_sardines)
h =  len(hor_sardines)
ans *= pow(2, v, MOD) + pow(2, h, MOD) - 1
ans %= MOD

z = len(zero_sardines)
ans += pow(2, v, MOD) - 1 
ans -= 1
ans %= MOD

print(ans)




### FIXED CODE ###

n = int(input())
MOD = 1000000007

ans = 1
x_sardines = []
ver_sardines = []
hor_sardines  = []
zero_sardines  = []

for _ in range(n):
  ai, bi = map(int, input().split())
  if ai == 0 and bi != 0:
    ver_sardines.append((ai, bi))
  elif ai != 0 and bi == 0:
    hor_sardines.append((ai, bi))
  elif ai == 0 and bi == 0:
    zero_sardines.append((ai, bi))
  elif bi / ai > 0:
    x_sardines.append((ai, bi, 1))
  elif bi / ai < 0:
    x_sardines.append((- 1 * bi, ai, -1))

x_sardines.sort(key = lambda x: x[1] / x[0])

if len(x_sardines) > 0:
  pai, pbi, ps = x_sardines[0]
  p = 1 if ps == 1 else 0
  n = 1 if ps == -1 else 0
  for i, (ai, bi, s) in enumerate(x_sardines[1:]):
    if pai * bi - pbi * ai != 0:
      ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
      ans %= MOD
      p = 0
      n = 0
      
    if s == 1:
      p += 1
    elif s == -1:
      n += 1
    pai, pbi, ps = ai, bi, s

  ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
  ans %= MOD
  
v = len(ver_sardines)
h = len(hor_sardines)
ans *= pow(2, v, MOD) + pow(2, h, MOD) - 1
ans %= MOD

z = len(zero_sardines)
ans += z
ans -= 1
ans %= MOD

print(ans)
a, b, c = map(int, input().solit())
if a + b >= c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a + b >= c:
    print("Yes")
else:
    print("No")
from collections import deque
s = deque(input().replace('\n', ''))
q = int(input())
flag = True
for i in range(q):
    query = list(map(str, input().split()))
    if query[0]=='1':
        if flag: flag = False
        else: flag = True
    else:
        
        if (not flag and query[1]=='1') or flag and query[1]=='2':
            s.append(query[2])
        else:
            s.appendleft(query[2])
if not flag:
    s = s[::-1]

print(''.join(s))


### FIXED CODE ###

from collections import deque
s = deque(input().replace('\n', ''))
q = int(input())
flag = True
for i in range(q):
    query = list(map(str, input().split()))
    if query[0]=='1':
        if flag: flag = False
        else: flag = True
    else:
        
        if (not flag and query[1]=='1') or flag and query[1]=='2':
            s.append(query[2])
        else:
            s.appendleft(query[2])
s = ''.join(s)
print(s if flag else s[::-1])
a,b,c,d = map(int, input().split())
print(max(a*b, c*d)

### FIXED CODE ###

a,b,c,d = map(int, input().split())
print(max(a*b, c*d))
N=int(input())
n=N%10
if n==2,4,5,7,9:
    ptint('hon')
elif n==0,1,6,8:
    print('pon')
else:
    print('bon')

### FIXED CODE ###

a = int(input())
a %= 10

if a==0 or a==1 or a==6 or a==8:
  print("pon")
elif a==3:
  print("bon")
else:
  print("hon")
a=input()
if a[1]==a[2]==a[3]:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

a=input()
if a[0]==a[1]==a[2]:
  print("No")
else:
  print("Yes")
top=0
sum=0
asp=0
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))

for i in range(n):
    sum=sum+a[i-1]
    if a[i-1]<a[i] or i==1:
        top=a[n-1]
asp=1-(1/(4*m))
    if top>sum*asp:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))

new_a=sorted(a,reverse=True)
sums=sum(a)

if new_a[m-1]>=sums/(m*4):
    print("Yes")
else:
    print("No")
N, M = map(int, input().split(" "))
AB = [list(map(int, input().split(" "))) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.per = list(range(n))
        self.point = n*(n-1) // 2
        self.counts = [1]*n

    def root(self, x):
        if self.per[x] == x:
            return x
        return self.root(self.per[x])

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        self.per[rx] = ry
        self.point -= self.counts[ry] * self.counts[rx]
        self.counts[ry] += self.counts[rx]
        self.counts[rx] = 0

    def is_same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


u = UnionFind(N)
results = []
for a, b in AB[::-1]:
    x, y = a-1, b-1
    u.union(x, y)
    results.append(u.point)

print(*results[::-1])


### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        self.par[ry] = rx
        return True

    def is_same(self, x, y):
        rx, ry = self.root(x), self.root(y)
        return rx == ry

    def get_size(self, x):
        return self.size[self.root(x)]


uf = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(uf.point)
    x, y = a-1, b-1
    uf.unite(x, y)

print(*results[::-1], sep="\n")
import numpy as np
N, M = map(int, input().split())
H = list(map(int, input().split()))
yoi = np.ones(M)
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        yoi[B-1] = 0
    elif H[B-1] > H[A-1]:
        yoi[A-1] = 0
    elif H[A-1]==H[B-1]:
        yoi[A-1] = 0
        yoi[B-1] = 0
print(int(np.sum(yoi)))

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
H = list(map(int, input().split()))
yoi = np.ones(N)
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        yoi[B-1] = 0
    elif H[B-1] > H[A-1]:
        yoi[A-1] = 0
    elif H[A-1]==H[B-1]:
        yoi[A-1] = 0
        yoi[B-1] = 0
print(int(np.sum(yoi)))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


import math


N, M = map(int, input().split())
uf = UnionFind(M)
for i in range(N):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
x=uf.group_count()
print(x)
print(math.ceil(math.log(x,2)))




### FIXED CODE ###


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())





N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
x=uf.group_count()
print(x-1)
S,T=list(input())
s,t=list(map(int, input().split()))
U=input()
if U==S:
  print(s-1,t)
else:
  print(s,t-1)


### FIXED CODE ###

S,T=input().split()
s,t=list(map(int, input().split()))
U=input()
if U==S:
  print(s-1,t)
else:
  print(s,t-1)
N,M=map(int,input().split())
numbers=[' ',]*N
kotae=0
for a in range(M):
    suuji=[]
    s,c=map(int,input().split())
    if numbers[s-1]==' ':
        numbers[s-1]=c
    else:
        if numbers[s-1]==c:
            continue
        else:
            print('-1')
            kotae+=1
            break

for a in range(3):
    if numbers[a]==' ':
        numbers[a]=0
if numbers[0]==0:
    del numbers[0]
    if numbers[0]==0:
        del numbers[0]
        if numbers[0]==0:
            del numbers[0]
if kotae==0:
    if len(numbers)!=N:
        print(-1)
    else:
       moji=''
       for a in numbers:
           moji+=str(a)
       print(int(moji))
       

### FIXED CODE ###

N,M=map(int,input().split())
numbers=[' ',]*N
kotae=0
for a in range(M):
    suuji=[]
    s,c=input().split()
    if numbers[int(s)-1]==' ':
        numbers[int(s)-1]=int(c)
    else:
        if numbers[int(s)-1]==int(c):
            continue
        else:
            print('-1')
            kotae+=1
            break
if numbers[0]==' ' and N==3:
    numbers[0]=1
if N==2 and numbers[0]==' ':
    numbers[0]=1
for a in range(N):
    if numbers[a]==' ':
        numbers[a]=0
if N==3:
    if numbers[0] == 0:
        del numbers[0]
        if numbers[0] == 0:
            del numbers[0]
            if numbers[0] == 0:
                del numbers[0]
if N==2:
    if numbers[0] == 0:
        del numbers[0]
        if numbers[0] == 0:
            del numbers[0]
if kotae==0:
    if len(numbers)!=N:
        print('-1')
    else:
       moji=''
       for a in numbers:
           moji+=str(a)
       print(int(moji))
inf = float('inf')
V,E,P = map(int,input().split())
edge = []
edge_rev = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge_rev.append([B-1,A-1,P-C])
    edge.append([A-1,B-1,P-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

d_rev = [inf]*V
d_rev[V-1] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

d_ = d.copy()
d_rev_ = d_rev.copy()

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

loop = False
for i in range(V):
    if d[i] != 0 and d_rev[i] != 0:
        loop = (d[i]+d_rev[i] != d_[i]+d_rev_[i]) or loop

if loop:
    print(-1)

else:
    ans = -d[-1]
    print(max(0,ans))

### FIXED CODE ###

inf = float('inf')
V,E,P = map(int,input().split())
edge = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge.append([A-1,B-1,P-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

ans = d[V-1]

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
loop = ans != d[V-1]

if loop:
    print(-1)

else:
    ans = -d[-1]
    print(max(0,ans))
A, B, K = map(int, input().split())

if (B-A+1) < K:
    for i in range(A, B+1):
        print(i)
    exit()

lst = list(range(A, B+1))
x = [lst[i] for i in range(0, K)]
y = [lst[i] for i in range(-1, -K-1, -1)]

ans = list(set(x) | set(y))
ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(b, a + k - 1) + 1):
    print(i)
for i in range(max(b - k + 1, a + k), b + 1):
    print(i)
def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()



### FIXED CODE ###

def main():
    N, W =map(int, input().split())

    weights = []
    values = []
    for i in range(N):
        wi, vi =map(int, input().split())
        weights.append(wi)
        values.append(vi)

    sum_v = sum(values)

    INF = 10**9+7

    dp = [[INF]*(sum_v+1) for _ in range(N+1)]
    dp[0][0] = 0


    for i in range(N):
        wi = weights[i]
        vi = values[i]
        for j in range(sum_v+1):
            if j < vi:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

    for j in range(sum_v+1):
        if dp[N][j] <= W:
            ans = j

    print(ans)

if __name__ == "__main__":
    main()
s,t=input().split()
a,b=map(int,input()split())
u=input()
if u==s:
    a-=1
else:  b-=1
print(a, b)

### FIXED CODE ###

s, t = input().split()
a, b = map(int, input().split())
u = input()
if u == s:
    a-= 1
else: b -= 1
print(a, b)
a=list(map(int,input().split()))
aa=list(range(a[0],a[1]+1))
z=aa.count(0)
n=sum([1 for i in aa if i<0])%2
if z>0:
  print('Zero')
elif n==0:
  print("Positive")
else:
  print("Negative")

### FIXED CODE ###

a,b=map(int,input().split())
a=min(1,a)
b=min(1,b)
if b==1 and a<=0:
  print('Zero')
elif b==0:
  print('Zero')
elif (b-a)%2==0 and b<0:
  print("Negative")
else:
  print("Positive")
from scipy.special import comb
n,m = map(int, input().split())

even = comb(n,2,exact=True) + comb(m,2,exact=True)

print(even)

### FIXED CODE ###

n,m = map(int, input().split())
all = (n+m)*(n+m-1)/2
print(int(all-m*n))
import sys

def plus_and_check(lines):
a, b = lines.split()
number = a + b
return len(str(number))

a = []
for line in sys.stdin:
    a.append(int(line))

answer = []
for i in range(len(a)):
    answer = plus_and_check(a[i])

for i in range(len(answer)):
    print answer[i]

### FIXED CODE ###

import sys

a = []
answer_array = []
for line in sys.stdin:
    a.append(map(int, line.strip().split()))
    #except StopIteration:
        #break

for i in range(len(a)):
    sum_up = a[i][0] + a[i][1]

    answer = len(str(sum_up))

    answer_array.append(answer)

for j in range(len(answer_array)):
    print answer_array[j]
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

total = 0

for i in range(N):
    low = 0
    high = N + 1
    while low < high:
        mid1 = (low + high) // 2
        if A[mid1] < B[i]:
            low = mid1 + 1
        else:
            high = mid1
    mid1 = low
    low = 0
    high = N + 1
    while low < high:
        mid2 = (low + high) // 2
        if C[mid2] <= B[i]:
            low = mid2 + 1
        else:
            high = mid2
    mid2 = high
    total = total + mid1 * (N - mid2)

print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
#A = [int(x) for x in input().split()]
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
A = [-float('inf')] + A + [float('inf')]
B.sort()
C.sort()
C = [-float('inf')] + C + [float('inf')]

total = 0

for i in range(N):
    low = 0
    high = N + 1
    while high - low > 1:
        mid1 = (low + high) // 2
        if A[mid1] < B[i]:
            low = mid1
        else:
            high = mid1
    mid1 = low
    low = 0
    high = N + 1
    while high - low > 1:
        mid2 = (low + high) // 2
        if C[mid2] <= B[i]:
            low = mid2
        else:
            high = mid2
    mid2 = high
    total += mid1 * (N + 1 - mid2)

print(total)
a,b,k=map(int,input().split())
printf(a-min(a,k),b-min(b,a-min(a,k))

### FIXED CODE ###

a,b,k=map(int,input().split())
print(a-min(a,k),b-min(b,k-min(a,k)))
n, m = map(int,input().split())
lst = []
for _ in range(m):
    lst.append(list(map(int,input().split())))

number = [[] for _ in range(n)]
for v in lst:
    keta,num = v[0]-1,v[1]
    if not number[keta]:
        number[keta] = num
    else:
        if number[keta] != num:
            print(-1)
            exit()
if n == 1:
    if number[0] == 0:
        print(0)
        exit()

    if not number[0]:
        number[0] = [0]
else:
    if not number[0]:
        number[0] = [1]

for i in range(m):
    if not number[i]:
        number[i] = 0

print(''.join([str(i) for i in number]))

### FIXED CODE ###

n, m = map(int,input().split())
lst = []
for _ in range(m):
    lst.append(list(map(int,input().split())))

number = [[] for _ in range(n)]
for v in lst:
    keta,num = v[0]-1,v[1]
    if number[keta] == []:
        number[keta] = num

    if number[keta] != num:
        print(-1)
        exit()

if n == 1:
    if not number[0]:
        print(0)
    else:
        print(''.join([str(i) for i in number]))
elif n == 2:
    if number[0] == 0:
        print(-1)
        exit()
    else:
        if not number[0]:
            number[0] = 1
        if not number[1]:
            number[1] = 0
        print(''.join([str(i) for i in number]))
else:
    if number[0] == 0:
        print(-1)
        exit()
    else:
        if not number[0]:
            number[0] = 1
        if not number[1]:
            number[1] = 0
        if not number[2]:
            number[2] = 0
        print(''.join([str(i) for i in number]))
s=input()
l=["+","-"]
for i in range(1):
  for j in range(i):
    for p in range(1):
      if eval(s[0]+l[i]+s[1]+l[j]+s[2]+l[p]+s[3])==7:
        break
print(s[0]+l[i]+s[1]+l[j]+s[2]+l[p]+s[3]+"=7")

### FIXED CODE ###

s=input()
c=0
l=["+","-"]
for i in range(2):
  if c!=0:
  	break
  for j in range(2):
    if c!=0:
      	break
    for p in range(2):
      if eval(s[0]+l[i]+s[1]+l[j]+s[2]+l[p]+s[3])==7:
        print(s[0]+l[i]+s[1]+l[j]+s[2]+l[p]+s[3]+"=7")
        c=1
        break
import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd,numbers)

n=int(input())
a=list(map(int,input().split()))
gcd_without_i=[gcd(a[:i]+a[i+1:]) for i in range(n)]

print(max(gcd_without_i))


### FIXED CODE ###

def gcd(a,b):
    if a*b<0:
        return -a*b
    while b!=0:
        tmp=a%b
        a=b
        b=tmp
    return a

# def gcd_list(numbers):
#     # print(numbers)
#     g=numbers[0]
#     for i in range(n-1):
#         g=gcd(g,numbers[i])
#     return g
#
# n=int(input())
# a=list(map(int,input().split()))
# gcd_without_i=[gcd_list(a[:i]+a[i+1:]) for i in range(n)]
# # print(gcd_without_i)
# print(max(gcd_without_i))

n=int(input())
a=list(map(int,input().split()))
# gcd_lhs[i]=gcd(a[0],...,a[i-1])
gcd_lhs=[-1 for _ in range(n)]
# gcd_rhs[i]=gcd(a[i+1],...,a[n-1])
gcd_rhs=[-1 for _ in range(n)]
gcd_lhs[1]=a[0]
gcd_rhs[n-2]=a[n-1]
for i in range(1,n):
    gcd_lhs[i]=gcd(gcd_lhs[i-1],a[i-1])
    gcd_rhs[n-1-i]=gcd(gcd_rhs[n-i],a[n-i])

gcd_without_i=[gcd(gcd_lhs[i],gcd_rhs[i]) for i in range(n)]
print(max(gcd_without_i))
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = dp[tmp][L]
    for j in range(1, 1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()