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

class MyClass():
    def main(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())
        
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        w = self.rec(m,self.A)
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])
        
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        elif len(A) == 1 or m_new < min(A[1:]):
            r2 = False
        else:
            r2 = self.rec(m_new,A[1:])
        
        if r1 or r2:
            return True
        else:
            return False
    
if __name__ == "__main__":
    MC = MyClass()
    MC.main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

import collections
from collections import defaultdict
N = int(input())
edges = []
vertexes = []
count = defaultdict(int)
parent = {}
childs = defaultdict(list)
color_dict = defaultdict(dict)
for i in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  childs[a].append(b)
  edges.append((a,b))
  vertexes.append(a)
  vertexes.append(b)
  
#print(edges)
#print(vertexes)
#print(parent)
#childs = dict(childs)
#print(childs)

c = collections.Counter(vertexes)
max_color = max(c.values())
print(max_color)

parent_color = {1: -1}
for i in range(1, N):
  if i not in childs:
    continue
  pc = parent_color[i]
  allowed_colors = [j for j in range(1, max_color + 1) if j != pc]
  for child, color in zip(childs[i], allowed_colors):
    color_dict[i][child] = color
    parent_color[child] = color
    
#print(color_dict)

for e in edges:
  print(color_dict[e[0]][e[1]])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

# make graph
# graph(x): xと繋がっている頂点（番号）のリスト
graph = [[] for _ in range(N+1)]
for a,b in AB:
  graph[a].append(b)
  graph[b].append(a)

# 深さ優先探索で、頂点の探索順序を作成
root = 1
parent = [0] * (N+1) # parent[x]: xの親の番号
order = [] # 深さ優先探索の順序リスト
stack = [root]
while stack:
  x = stack.pop()
  order.append(x)
  for y in graph[x]:
    if y == parent[x]:
      continue
    parent[y] = x
    stack.append(y)

# color[i]: 頂点iとその親の間の辺の色
color = [-1] * (N+1)

# 頂点の探索順ごとに、頂点とその子の間の辺の色を決定
for x in order:
  ng = color[x] # 頂点xとxの親との間の辺の色
  c = 1
  # 頂点xとつながっている頂点のリストを取得し、辺の色を1から順に割り当てる
  for y in graph[x]:
    if y == parent[x]: # xの親の頂点の場合は何もしない
      continue
    if c == ng: # xとその親との間の辺の色は割り当てないようにする
      c += 1
    color[y] = c
    c += 1

# 回答作成
answer = []
for a,b in AB:
  # aがbの子ならcolor[a]を、逆の場合はcolor[b]を出力する
  if parent[a] == b:
    answer.append(color[a])
  else:
    # 今回の場合、a_i < b_iで、番号の小さい方が親になるように木を作っているので、
    # こちらの条件のほうにしか引っかからないはず
    answer.append(color[b])

K = max(answer) # 色の番号の中で最も大きいものがK
print(K)
print('\n'.join(map(str,answer)))
### BUGGY CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

print(ans)


### FIXED CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
points_matrix = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if (points_matrix[i][k] + points_matrix[j+1][l+1] - points_matrix[i][l+1] - points_matrix[j+1][k]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

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

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

MOD = 998244353

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

ans = 0

for i, x in enumerate(a):
    if x < s:
        dp[i+1][x] = i + 1
    if x == s:
        ans = (ans + (n-i) * (i+1)) % MOD
    for j in range(1, s):
        if dp[i][j] > 0:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            if j + x < s:
                dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j]) % MOD
            elif j + x == s:
                ans = (ans + dp[i][j] * (n-i)) % MOD

print(ans)

### FIXED CODE ###

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

MOD = 998244353

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

ans = 0

for i, x in enumerate(a):
    if x < s:
        dp[i+1][x] = i + 1
    if x == s:
        ans = (ans + (n-i) * (i+1)) % MOD
    for j in range(1, s):
        if dp[i][j] > 0:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            if j + x < s:
                dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j]) % MOD
            elif j + x == s:
                ans = (ans + dp[i][j] * (n-i)) % MOD

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

n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  s[0]=min(s[0],n)
  for i in range(1,n):
    s[i]=min(s[i-1]+s[i],n)
  if s==l[:n]: break
  l=s[:n]
print(*l)

### FIXED CODE ###

n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,99)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)
### BUGGY CODE ###

from sys import stdin
import math

N = int(input())
S = input()


count_r = S.count('R')
count_g = S.count('G')
count_b = S.count('B')

total = count_r * count_g * count_b

for i in range(1, len(S)):
    for j in range(len(S)):
        if j+i+i >= len(S):
            continue
        if S[j] != S[j+i] and S[j+i] != S[j+i+i] and S[j] != S[j+i+i]:
            total -= 1

print(total)


### FIXED CODE ###

N = int(input())
S = input()


total = S.count('R') * S.count('G') * S.count('B')


for gap in range(1, N//2+1):
    for i in range(N - 2 * gap):
        j = i + gap
        k = j + gap
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            total -= 1

print(total)
### BUGGY CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    prime_his = []
    for a in A:
        d = primes(a)
        for key in d.keys():
            if key in prime_his:
                return "setwise coprime"
        prime_his = prime_his + list(d.keys())
    
    return "pairwise coprime"

    
print(solve())

### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    history = {}
    for i in range(10**6):
        history[i] = 0

    for a in A:
        d = primes(a)
        for key in d.keys():
            history[key] += 1
            if history[key] > 1:
                return "setwise coprime"
    return "pairwise coprime"
 
    
print(solve())
### BUGGY CODE ###

n,m = map(int,input().split())
a_list = []
li = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c = list(map(int,input().split()))
    for j in range(b):
        c[j] -= 1
    li.append(c)

min_coin = 10**10

for i in range(2**m):
    bool_list = []
    coin = 0
    for j in range(m):
        if (i >> j)&1:
            for k in li[j]:
                bool_list += li[j]
            coin += a_list[j]
    bool_list = set(bool_list)
    if len(bool_list) != n:
        continue
    min_coin = min(min_coin,coin)

if min_coin == 10**10:
    print(-1)
else:
    print(min_coin)

### FIXED CODE ###

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import bisect
n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
rui = []
now = 0
pl = []
for i in range(n):
    now += a[i]
    rui.append(now)
l = [[0 for i in range(s)] for i in range(n)]
ans = 0
for i in range(n):
    if a[i] < s:
        l[i][a[i]] += i+1
    elif a[i] == s:
        ans += i*(n-i-1)
        ans += n
        ans %= mod
    for j in range(s):
        if i > 0:
            if l[i-1][j] > 0:
                if j+a[i] < s:
                    l[i][j+a[i]] += l[i-1][j]
                elif j+a[i] == s:
                    ans += l[i-1][j]*(n-i)
                    ans %= mod
                l[i][j] += l[i-1][j]
print(ans)

### FIXED CODE ###

n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
rui = []
now = 0
pl = []
for i in range(n):
    now += a[i]
    rui.append(now)
l = [[0 for i in range(s)] for i in range(n)]
ans = 0
for i in range(n):
    if a[i] < s:
        l[i][a[i]] += i+1
        l[i][a[i]] %= mod
    elif a[i] == s:
        ans += i*(n-i-1)
        ans += n
        ans %= mod
    for j in range(s):
        if i > 0:
            if l[i-1][j] > 0:
                if j+a[i] < s:
                    l[i][j+a[i]] += l[i-1][j]
                    l[i][j+a[i]] %= mod
                elif j+a[i] == s:
                    ans += l[i-1][j]*(n-i)
                    ans %= mod
                l[i][j] += l[i-1][j]
                l[i][j] %= mod
print(ans)
### BUGGY CODE ###

import sys
n=int(input())
s=list(input())
m=10**9+7
if s[0]=='W' or s[2*n-1]=='W':
  print(0)
  sys.exit()
side=[]
l=['L','R']
for i in range(2*n):
  if i==0:
    side.append('L')
  else:
    if s[i-1]==s[i]:
      side.append(l[(l.index(side[i-1])+1)%2])
    else:
      side.append(l[l.index(side[i-1])])
ctL=0;ctR=0;ans=1
for i in range(2*n):
  if side[i]=='L':
    ctL+=1
  else:
    ans=ans*(ctL-ctR)
    ctR+=1
if ctL!=ctR:
  print(0)
  sys.exit()
for i in range(1,n+1):
  ans*=i
  ans%=m
print(ans)

### FIXED CODE ###

import sys
n=int(input())
s=list(input())
m=10**9+7
if s[0]=='W' or s[2*n-1]=='W':
  print(0)
  sys.exit()
side=[]
l=['L','R']
for i in range(2*n):
  if i==0:
    side.append('L')
  else:
    if s[i-1]==s[i]:
      side.append(l[(l.index(side[i-1])+1)%2])
    else:
      side.append(l[l.index(side[i-1])])
ctL=0;ctR=0;ans=1
for i in range(2*n):
  if side[i]=='L':
    ctL+=1
  else:
    ans=ans*(ctL-ctR)
    ans%=m
    ctR+=1
if ctL!=ctR:
  print(0)
  sys.exit()
for i in range(1,n+1):
  ans*=i
  ans%=m
print(ans)
### BUGGY CODE ###

n = int(input())
alist = list(map(int, input().split()))

for i in range(1,n+1):
  ilist = [s for s in alist if s==i]
  print(len(ilist))

### FIXED CODE ###

n = int(input())
alist = list(map(int, input().split(" ")))
dp = [0]*n

for i in alist:
  dp[i-1]+=1

for i in dp:
  print(int(i))
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    R, C, K = map(int, input().split())

    field = [[0 for j in range(C)] for i in range(R)]

    for _ in range(K):
        r, c, v = map(int, input().split())
        field[r - 1][c - 1] = v

    dp = [[[0] * 4 for j in range(C)] for i in range(R)]

    for i in range(R):
        for j in range(C):
            ct = field[i ][j ]
            if ct == 0:
                dp[i][j][0] = max(dp[i][j - 1][0], max(dp[i - 1][j]))

                for k in range(1, 4):
                    if j>0:
                        dp[i][j][k] = dp[i][j - 1][k]
            else:
                dp[i][j][0] = max(dp[i][j - 1][0], max(dp[i - 1][j]))
                dp[i][j][1] = max(ct + max(dp[i][j - 1][0], max(dp[i - 1][j])),dp[i][j-1][1])
                for k in range(2, 4):
                    if j >0:
                        dp[i][j][k] = max(dp[i][j - 1][k - 1] +ct,dp[i][j-1][k])

    print(max(dp[R-1][C-1]))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    R, C, K = map(int, input().split())

    field = [[0 for j in range(C)] for i in range(R)]

    for _ in range(K):
        r, c, v = map(int, input().split())
        field[r - 1][c - 1] += v

    dp = [[0] * 4 for j in range(C)]

    for i in range(R):
        for j in range(C):
            ct = field[i][j]
            premax = max(dp[j])

            if ct == 0:
                if j>0:
                    dp[j][0] = max(dp[j - 1][0], premax)
                else:
                    dp[j][0] = premax

                for k in range(1, 4):
                    if j > 0:
                        dp[j][k] = dp[j - 1][k]
            else:
                if j>0:
                    dp[j][0] = max(dp[j - 1][0], premax)
                    dp[j][1] = max(ct + max(dp[j - 1][0], premax), dp[j - 1][1])
                else:
                    dp[j][0] = premax
                    dp[j][1] = premax +ct
                for k in range(2, 4):
                    if j > 0:
                        dp[j][k] = max(dp[j - 1][k - 1] + ct, dp[j - 1][k])

    print(max(dp[C - 1]))


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

s = input()
n = len(s)
x, y = map(int, input().split())
for i in range(n):
    if s[i]=='T':
        break
else:
    i += 1
x -= i
xs = {}
ys = {}
now = 0
xy = 'y'
for j in range(i+1, n+1):
    if j<n and s[j]=='F':
        now += 1
        continue
    if xy=='x':
        if now>0:
            if now not in xs:
                xs[now] = 0
            xs[now] += 1
        xy = 'y'
    else:
        if now>0:
            if now not in ys:
                ys[now] = 0
            ys[now] += 1
        xy = 'x'
    now = 0

def dfs(li, idx, now, target):
    if idx==len(li):
        return now==target
    for i in range(li[idx][1]+1):
        if dfs(li, idx+1, now+li[idx][0]*(li[idx][1]-2*i), target):
            return True
    return False

ans = dfs(list(xs.items()), 0, 0, x) and dfs(list(ys.items()), 0, 0, y)
print('Yes' if ans else 'No')

### FIXED CODE ###

s = input()
n = len(s)
x, y = map(int, input().split())
for i in range(n):
    if s[i]=='T':
        break
else:
    i += 1
dp = {i}
xs = []
ys = []
now = 0
xy = 'y'
for j in range(i+1, n+1):
    if j<n and s[j]=='F':
        now += 1
        continue
    if xy=='x':
        if now>0:
            xs.append(now)
        xy = 'y'
    else:
        if now>0:
            ys.append(now)
        xy = 'x'
    now = 0

for i in xs:
    newdp = set()
    for j in dp:
        newdp.add(j+i)
        newdp.add(j-i)
    dp = newdp
if x not in dp:
    print('No')
    exit(0)
dp = {0}
for i in ys:
    newdp = set()
    for j in dp:
        newdp.add(j+i)
        newdp.add(j-i)
    dp = newdp
if y in dp:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n = int(input())
  if n < 4:
    print(0)
    exit()
  ans = 0
  s = list(input())
  for i, a in enumerate(s):
    j = i+1
    k = i+2
    for bi, b in enumerate(s[j:]):
      if a == b:
        continue
      bb = bi+j
      for ci, c in enumerate(s[k:]):
        if a == c or b == c:
          continue
        cc = ci+k
        if i < bb < cc:
          if bb - i == cc - bb:
            continue
          ans += 1
  print(ans)          
import math
import fractions
import collections
import itertools
from functools import reduce
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n = int(input())
    s = input()
    R, G, B = [], [], []
    for i in range(n):
        index = i+1
        if s[i] == "R":
            R.append(index)
        elif s[i] == "G":
            G.append(index)
        elif s[i] == "B":
            B.append(index)
    all_count = len(R)*len(G)*len(B)
    count = 0
    # j - i != k - j
    # k = 2j - i
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            k = 2*j - i
            if k >= n:
                continue
            if s[k] == s[i] or s[k] == s[j]:
                continue
            count += 1
    print(all_count - count)

def bi(num, a, b, x):
    print((a * num) + (b * len(str(b))))
    if (a * num) + (b * len(str(b))) <= x:
        return False
    return True

def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


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

n = int(input())
alist = [int(s) for s in input().split(" ")]

import copy
a_ans = []
for i in range(n):
  atmp = copy.copy(alist)
  del atmp[i]
  ans = atmp[0]
  for a in atmp[1:]:
    ans ^= a
  a_ans.append(ans)
print(" ".join([str(a) for a in a_ans]))

### FIXED CODE ###

n = int(input())
alist = [int(s) for s in input().split(" ")]
asum = alist[0]
for a in alist[1:]:
  asum ^= a

import copy
a_ans = []
for i in range(n):
  asum ^= alist[i]
  a_ans.append(asum)
  asum ^= alist[i]
print(" ".join([str(a) for a in a_ans]))
### BUGGY CODE ###

#DP E
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

### FIXED CODE ###

#DP E
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
mod = 2019

t = [0]*n
dp = [0]*2020
t[0] = int(s[-1])
dp[t[0]] += 1
for i in range(n-1):
    t[i+1] = t[i] + int(s[-2-i])*pow(10, i+1)
    t[i+1] %= mod
    dp[t[i+1]] += 1
ans = 0
for D in dp[1:]:
    ans += D*(D-1)//2
print(ans+(dp[0]+1)*(dp[0])//2)




### FIXED CODE ###

s = input()
n = len(s)
mod = 2019

t = [0]*n
dp = [0]*2020
t[0] = int(s[-1])
dp[t[0]] += 1
for i in range(n-1):
    t[i+1] = t[i] + int(s[-2-i])*pow(10, i+1, mod)
    t[i+1] %= mod
    dp[t[i+1]] += 1
ans = 0
for D in dp[1:]:
    ans += D*(D-1)//2
print(ans+(dp[0]+1)*(dp[0])//2)
### BUGGY CODE ###

k = int(input())

if k % 2 == 0:
  print(-1)
  exit()

a = [7]
ans = 0
for i in a:
  if i % k == 0:
    ans += 1
    break
  else:
    a += [i*10 + 7]
    ans += 1


print(ans)

### FIXED CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
  print(-1)
  exit()

a = 7
ans = 0
for i in range(10**7):
  a = a % k
  if a % k == 0:
    ans = i + 1
    break
  else:
    a = a*10 + 7
    ans = i + 1


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

N, K = map(int, input().split())

mod = 10 ** 9 + 7

memo = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
    tmp = (K // i) ** N
    j = 2
    while i * j <= K:
        tmp -= memo[i * j]
        j += 1
    memo[i] = tmp
ans = 0
for i in range(1, K+1):
    ans += (memo[i] * i) % mod
    ans %= mod

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())

mod = 10 ** 9 + 7

memo = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
    memo[i] = pow(K // i, N, mod)
    j = 2
    while i * j <= K:
        memo[i] -= memo[i * j]
        j += 1
    ans += memo[i] * i
    ans %= mod

print(ans)