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

#https://atcoder.jp/contests/abc110/tasks/abc110_c

s = list(str(input()))
t = list(str(input()))
u = []
v = []
cnt = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if s[i] == s[j]:
            cnt += 1
    u.append(cnt)
    cnt = 0

cnt = 0
for i in range(len(t)):
    for j in range(i, len(t)):
        if t[i] == t[j]:
            cnt += 1
    v.append(cnt)
    cnt = 0

flag = 'Yes'
for i in range(len(u)):
    if u[i] != v[i]:
        flag = 'No'
        break

print(flag)

### FIXED CODE ###

import sys
s = str(input())
t = str(input())
l = len(s)
tmp = [[], []]
for i in range(l):
    if (not s[i] in tmp[0]) and (not t[i] in tmp[1]):
        tmp[0].append(s[i])
        tmp[1].append(t[i])
    else:
        if s[i] in tmp[0]:
            tmp2 = 0
            for j in range(len(tmp[0])):
                if s[i] == tmp[0][j]:
                    tmp2 = j
            if t[i] != tmp[1][tmp2]:
                print('No')
                sys.exit()
        else:
            print('No')
            sys.exit()
print('Yes')
### BUGGY CODE ###

import sys
import copy
import re
n, k = [int(i) for i in sys.stdin.readline().split()]
s = input()
def _reverse(text):
    res = text[::-1]
    res = ["R" if i == "L" else "L" for i in res]
    res = "".join(res)
    return res
"""
for i in range(k):
    left = s.find("R")
    left = 0 if left == -1 else left
    right = s.rfind("R") + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
s = copy.deepcopy(s_origi)
"""
for i in range(k):
    left = s.find("LR") + 1
    left = 0 if left == -1 else left
    right = s.rfind("RL")
    right = n if right == -1 else right + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
print(cnt)

### FIXED CODE ###

import re
n, k = [int(i) for i in input().split()]
s = input()
cnt = sum([1 for i in range(n-1) if s[i+1] == s[i]])
flg = (s[-1] == "R") + (s[0] == "R")
s += "L"
red_ls = re.findall(r"RL", s)
if len(red_ls) > k:
    print(cnt + k * 2)
else:
    if flg > 0:
        print(cnt + (len(red_ls) - flg) * 2 + flg)
    else:
        print(cnt + len(red_ls) * 2)
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
s=0
for i in range(N):
    for j in range(i+1,N):
        t=bin(A[i] ^ A[j])
        s+=int(t,0)
        s%=(10**9+7)
print(s)

### FIXED CODE ###

N = int(input())
A=list(map(int,input().split()))
L=[0]*65
MOD=(10**9+7)
for i in range(N):
    t=str(format(A[i],"b"))
    for j in range(len(t)):
        L[j]+=int(t[-j-1])

for i in range(len(L)):
    L[i]=L[i]*(N-L[i])
    L[i]*=2**i
    L[i]%=MOD
print(sum(L)%MOD)
### BUGGY CODE ###

N = int(input())
#A = [0]*N
A = list(map(lambda x: int(x)-1, [input() for n in range(N)]))

count = [-1]*N
n = 0
ans = 1
while A[n] != 2-1:
  n = A[n]
  if n in count:
    ans = -1
    break
  count[n] = n
  ans += 1
  
print(ans)

### FIXED CODE ###

n = int(input())
al = []
for i in range(n):
    a = int(input())
    al.append(a)
 
al.insert(0, 0)
ans = -1
push = 1
for i in range(1, n+2):
    light = al[push]
    push = light
    if light == 2:
        ans = i
        break
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())
part_list = []
# o(n^2)
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        part = s[i:j]
        part_list.append(part)
part_list = list(set(part_list))
part_list.sort()
ans = part_list[K-1]
print(ans)

### FIXED CODE ###

s = input()
K = int(input())
dict1 = {}
for i in range(len(s)):
    if s[i] in dict1:
        continue
    else:
        dict1[s[i]] = len(s) - i
dict1 = list(dict1.items())
dict1.sort()
count = 0
for e in dict1:
    count += e[1]
    if count >= K:
        note = e[0]
        break
part_list = []
for i in range(len(s)):
    if ord(s[i]) <= ord(note):
        for j in range(i+1,i+6):
            part = s[i:j]
            part_list.append(part)
part_list = list(set(part_list))
part_list.sort()
ans = part_list[K-1]
print(ans)
### BUGGY CODE ###


import os
import sys
from io import BytesIO, IOBase

def knapsack(wt,price,n,c,dp):
    if n<0 or c==0:
        return 0
    if dp[n][c]!=-1:
        return dp[n][c]
    inc=exc=0
    if c>=wt[n]:
        inc=price[n]+knapsack(wt,price,n-1,c-wt[n],dp)
    exc=0+knapsack(wt,price,n-1,c,dp)
    dp[n][c]=max(inc,exc)
    return max(inc,exc)

def main():
    n,c=map(int,input().split())
    wt=[]
    price=[]
    for _ in range(n):
        w,v=map(int,input().split())
        wt.append(w)
        price.append(v)
    dp=[[-1 for x in range(c+1)] for y in range(n+1)]
    print(knapsack(wt,price,n-1,c,dp))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

### FIXED CODE ###

def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)
    
    return dp[n][c]
  
n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))
### BUGGY CODE ###

N=int(input())
arr=[list(map(int,input().split())) for i in range(N)]

dis=[[] for i in range(N)]

for i in range(N):
    for j in range(N):
        dis[i].append((abs(arr[i][0]-arr[j][0])+abs(arr[i][1]-arr[j][1])))

ans=0
for i in range(N):
    ans=max(ans,max(dis[i]))

print(ans)

### FIXED CODE ###

N=int(input())
arr=[list(map(int,input().split())) for i in range(N)]

za,wa=-10**10,-10**10
zi,wi=10**10,10**10
for i in range(N):
    z=arr[i][0]+arr[i][1]
    w=arr[i][0]-arr[i][1]
    
    za=max(z,za)
    zi=min(z,zi)
    
    wa=max(w,wa)
    wi=min(w,wi)

print(max(za-zi,wa-wi))
### BUGGY CODE ###

input1 = input()
kbai= int(input1)
 
input2=input().split(" ")
mins= int(input2[0])
maxs= int(input2[1])
flg=0
ans=0
 
while flg == 0:
  ans=ans+kbai
  if ans > mins and ans <= maxs:
    flg=1

if flg ==1:
  print("OK")
  #print(ans,maxs,mins,flg)
else:
  print("NG")
  #print(ans,maxs,mins,flg)


### FIXED CODE ###

#
#at coder beginner contest165 a we love golf
#
import math

input1 = input()
kbai= int(input1)
 
input2=input().split(" ")
mins= int(input2[0])
maxs= int(input2[1])
flg=0
ans=0
tmp=0

tmp=math.floor(mins/kbai)
ans=tmp*kbai
#print(tmp)

while ans <= maxs:
  if ans >= mins and ans <= maxs:
    flg=1
  ans=ans+kbai

if flg ==1:
  print("OK")
  #print(ans,maxs,mins,flg)
else:
  print("NG")
  #print(ans,maxs,mins,flg)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,ma,mb = map(int, input().split())
abc = []
sa = 0
sb = 0
for _ in range(n):
    a,b,c = map(int, input().split())
    sa += a
    sb += b
    abc.append((a,b,c))
inf = 10**5
dp = [[[inf for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    a,b,c = abc[i]
    for ai in range(sa+1):
        for bi in range(sb+1):
            dp[i+1][ai][bi] = min(dp[i+1][ai][bi], dp[i][ai][bi])
            if ai+a<sa+1 and bi+b<sb+1:
                dp[i+1][ai+a][bi+b] = min(dp[i+1][ai+a][bi+b], dp[i][ai][bi]+c)
# print(dp)

res = inf
for ai in range(1,sa+1):
    for bi in range(1,sb+1):
        if ma*bi==mb*ai:
            res = min(res, dp[n][ai][bi])
if res == inf:
    print(-1)
else:
    print(res)


### FIXED CODE ###

# -*- coding: utf-8 -*-
inf = 10**10
n,ma,mb = map(int, input().split())

a = []
b = []
c = []
for _ in range(n):
    x,y,z = map(int, input().split())
    a.append(x)
    b.append(y)
    c.append(z)

memo = {}
def rec(i, maj, mbj):
    k = str(i)+"-"+str(maj)+"-"+str(mbj)
    if k in memo:
        return memo[k]
    # print(i, ":", maj, mbj, maj/ma, mbj/mb)
    ret = 0
    if i==n:
        if maj>0 and mbj>0 and maj/ma == mbj/mb:
            ret = 0
        else:
            ret = inf
    elif maj>0 and mbj>0 and maj/ma == mbj/mb:
        ret = 0
    else:
        r1 = rec(i+1, maj, mbj) # i番目を使わない場合
        # i番目を使う場合
        r2 = rec(i+1, maj+a[i], mbj+b[i]) + c[i]
        if r1>0 and r2==0:
            ret = r1
        elif r1==0 and r2>0:
            ret = r2
        else:
            ret = min(r1,r2)
    memo[k] = ret
    return ret

ret = rec(0, 0, 0)
if ret == inf:
    print(-1)
else:
    print(ret)
### BUGGY CODE ###

n,a,b,k=map(int,input().split())
mod=998244353
ans=0
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((i+1)*p[i])%mod
for ai in range(n+1):
    if k-a*ai>=0 and (k-a*ai)%b==0:
        bi=(k-a*ai)//b
        if bi<=n:
            ans+=p[n]*pow(p[ai],mod-2,mod)*pow(p[n-ai],mod-2,mod)*p[n]*pow(p[bi],mod-2,mod)*pow(p[n-bi],mod-2,mod)
            ans%=mod
print(ans)

### FIXED CODE ###

n,a,b,k=map(int,input().split())
mod=998244353
ans=0
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((i+1)*p[i])%mod
for ai in range(n+1):
    if k-a*ai>=0 and (k-a*ai)%b==0:
        bi=(k-a*ai)//b
        if bi<=n:
            ans+=p[n]*pow(p[ai],mod-2,mod)*pow(p[n-ai],mod-2,mod)*p[n]*pow(p[bi],mod-2,mod)*pow(p[n-bi],mod-2,mod)
            ans%=mod
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)
### BUGGY CODE ###

n=int(input())
c=list(map(int,input().split()))
for i in range(1,n+1):
    print(c.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = dict()
for i in range(n):
    d[i] = 0
for e in a:
    d[e-1] += 1
for i in range(n):
    print(d[i])
### BUGGY CODE ###

import heapq
def main():
    x, y, a, b, c = map(int,input().split())
    p_ins = list(map(int,input().split()))
    q_ins = list(map(int,input().split()))
    r_ins = list(map(int,input().split()))
    p = select(p_ins, x)
    q = select(q_ins, y)
    r = select(r_ins, min(c, x + y))
    res = 0
    for _ in range(x + y):
        if p[-1] <= r[-1] and q[-1] <= r[-1]:
            t = r.pop()
            res += t
        elif p[-1] <= q[-1]:
            t = q.pop()
            res += t
        else:
            t = p.pop()
            res += t
    print(res)

def select(array, length):
    ins = []
    res_l = []
    for part in array:
        heapq.heappush(ins,-part)
    for _ in range(length):
        res = heapq.heappop(ins)
        res_l = [-res] + res_l
    return [0] + res_l


if __name__ == "__main__":
    main()


### FIXED CODE ###

import heapq
def main():
    x, y, a, b, c = map(int,input().split())
    p = list(map(int,input().split()))
    q = list(map(int,input().split()))
    r = list(map(int,input().split()))
    pp = select(p, x)
    qq = select(q, y)
    res = select(pp + qq + r, x + y)
    print(sum(res))



def select(array, length):
    ins = []
    res_l = []
    for part in array:
        heapq.heappush(ins,-part)
    for _ in range(length):
        res = heapq.heappop(ins)
        res_l.append(-res)
    return res_l


if __name__ == "__main__":
    main()
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
    if a>=1:
        a-=1
    elif a==0 and b>=1:
        b-=1
print(a,b)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
    print(a-k,b)
elif a<k and b>=k-a:
    print(0,b-(k-a))
else:
    print(0,0)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
S = input()
Q = int(input())

state = 1 # 反転していたら-1
for i in range(Q):
    q = input()
    if q == '1':
        state *= -1
    else:
        Y, f, c = q.split()
        if (state == 1 and f == '1') or (state == -1 and f == '2'):
            S = c + S
        elif (state == 1 and f == '2') or (state == -1 and f == '1'):
            S = S + c

if state == -1:
    S = S[::-1]
print(S)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())

state = 1 # 反転していたら-1
Stock = deque([S])
for i in range(Q):
    q = input()
    if q == '1':
        state *= -1
    else:
        Y, f, c = q.split()
        if (state == 1 and f == '1') or (state == -1 and f == '2'):
            Stock.appendleft(c)
        elif (state == 1 and f == '2') or (state == -1 and f == '1'):
            Stock.append(c)
S = ''.join(Stock)
if state == -1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        # self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
# for i in range(1,n + 1):
#     dp[i][0].angle = Angle.UP
# for j in range(1,m + 1):
#     dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1].value = dp[i][j].value + 1
            dp[i + 1][j + 1].ans = "".join([dp[i][j].ans, s[i]])
        elif dp[i][j + 1].value > dp[i + 1][j].value: #UP
            dp[i + 1][j + 1].ans = dp[i][j + 1].ans
            dp[i + 1][j + 1].value = dp[i][j + 1].value
        else:  # LEFT
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
            dp[i + 1][j + 1].value = dp[i + 1][j].value

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

sum = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)


for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i, j, k)

print(sum)


### FIXED CODE ###

import math

K = int(input())
sum = 0

for i in range(K):
    for j in range(K):
        tmp = math.gcd(i+1, j+1)
        for k in range(K):
            sum += math.gcd(tmp, k+1)
        
print(sum)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

for t in T:
    if t in D:
        D.remove(t)
    else:
        print("NO")
        exit()

print("YES")

### FIXED CODE ###

N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

dictD = {}
for d in D:
    if d in dictD:
        dictD[d] += 1
    else:
        dictD[d] = 1

dictT = {}
for t in T:
    if t in dictT:
        dictT[t] += 1
    else:
        dictT[t] = 1


for k, v in dictT.items():
    if k in dictD:
        if v > dictD[k]:
            print("NO")
            exit()
    else:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[[0]*(we+1) for _ in range(n+1)]

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

### FIXED CODE ###

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[[0]*(we+1) for _ in range(n+1)]

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )