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

import itertools
from sys import stdin
N=list(map(int,stdin.readline().strip().split()))[0]
st=list(stdin.readline().strip())
count=0
stt=set(st)
stt=list(stt)
num=['0','1','2','3','4','5','6','7','8','9']
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    cnt = 0
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
l = []
ans = 0
for x in a:
    if x not in l:
        num = a.count(x)
        if num > x:
            ans += num-x
        if num < x:
            ans += num
        l.append(x)
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
l = collections.Counter(a)
ans = 0
for x in l:
    if l[x] > x:
        ans += l[x]-x
    if l[x] < x:
        ans += l[x]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()
a = [int(input()) for i in range(m)]

l = [0] * (n+1)
l[0] = 1
h = list(range(n+1))
for i in a:
    h.remove(i)
for i in h:
     if i == 1:
        l[i] = 1
     elif i >= 2:
        l[i] = l[i-1] + l[i-2]
        l[i] %= 1000000007


#print(l)
print(l[n] % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

l = [0] * (n+1)
l[0] = 1

a = 0
if m != 0:
    a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())



#print(l)
print(l[n] % 1000000007)
### BUGGY CODE ###

s=input()
q=int(input())
hanten=0

for i in range(q):
    s1=input()
    if len(s1)==1:
        hanten+=1
    else:
        a,f,c=s1.split()
        f=int(f)
        if f==1:
            if hanten%2==0:
                s = c + s
            else:
                s = s + c
        else:
            if hanten%2==0:
                s = s + c
            else:
                s = c + s
        

if hanten%2==0:
    print(s)
else:
    s2=""
    for i in range(len(s)):
        s2 += s[-(i+1)]
    print(s2)

                


### FIXED CODE ###

s=input()
q=int(input())
hanten=0
s_1 = ""
s_2 = ""

for i in range(q):
    s1=input()
    if len(s1)==1:
        hanten+=1
    else:
        a,f,c=s1.split()
        f=int(f)
        if (f+hanten)%2==0:
            s_2 += c
        else:
            s_1 = c + s_1     

if hanten%2==0:
    print(s_1 + s + s_2)
else:
    s_3 = s_1 + s + s_2
    print(s_3[::-1])
### BUGGY CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

stack=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            stack.append((i,j))


dh=[1,0,-1,0]
dw=[0,1,0,-1]

cnt=0
while stack:
    nstack=[]
    for h,w in stack:
        for k in range(4):
            th=h+dh[k]
            tw=w+dw[k]
            if not board[th][tw]:
                board[th][tw]=True
                nstack.append((th,tw))
    stack=nstack
    cnt+=1

print(cnt-1)

### FIXED CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)
### BUGGY CODE ###

n, q=map(int, input().split())
s=list(input())
l_list=[]
r_list=[]
for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)

for i in range(q):
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    for i in range(len(target_s)-1):
        if target_s[i]=="A":
            if target_s[i+1]=="C":
                count=count+1
    print(count)


### FIXED CODE ###

n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

from decimal import *
getcontext().prec = 1000000
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt()<Decimal(c).sqrt():
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if 4*a*b<(c-a-b)*(c-a-b) and c>a+b:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
A = [input() for _ in range(H)]

count = [[0]*W for _ in range(H)]
q = deque([])

for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			q.append((i, j))
# print(q)

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while len(q) >= 1:
	i, j = q.popleft()
	# print(i, j)
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "#":
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

ans = 0
for i in range(H):
	ans = max(ans, max(count[i]))
# print(count)
print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
A = [input() for _ in range(H)]

count = [[0]*W for _ in range(H)]
q = deque([])

for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			q.append((i, j))
# print(q)

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while len(q) >= 1:
	i, j = q.popleft()
	# print(i, j)
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "#":
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

ans = 0
for i in range(H):
	ans = max(ans, max(count[i]))
# print(count)
print(ans)
### BUGGY CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    a = abs(A[i]-A[j])
    ans = max(ans, min(a, K-a))
print (K-ans)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
ans = min(A[-1]-A[0],K-(A[-1]-A[0]))
for i in range(N-1):
  ans = max(ans,A[i+1]-A[i])
print (K-ans)
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
c=0
for i in range(n):
  c1=min(l[:i+1])
  if(l[i]==c1):
    c+=1
print(c)

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l1=[]
c=0
l1.append(l[0])
for i in range(1,n):
  l1.append(min(l1[i-1],l[i]))
for i in range(n):
  if(l[i]==l1[i]):
    c+=1
print(c)
### BUGGY CODE ###

n = int(input())
x_bin = input()
x = int(x_bin, 2)

def solve(a, pc):
    ans = 0
    while a != 0:
        a = a % pc
        pc = bin(a).count('1')
        ans += 1
    return ans
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1

for i in reversed(range(n)):
    if x_bin[n-i-1] == '1':
        a = x - pow(2, i)
        print(solve(a, pc_m))
    else:
        a = x + pow(2, i)
        print(solve(a, pc_p))


### FIXED CODE ###

n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)
### BUGGY CODE ###

N = int(input())
ss = []
for _ in range(N):
    ss.append(''.join(sorted(input())))

result = 0
for u in set(ss):
    cnt = len([s for s in ss if s == u])
    result += (cnt * (cnt -1)) / 2
print(int(result))


### FIXED CODE ###

N = int(input())
ss = []
for _ in range(N):
    ss.append(''.join(sorted(input())))
d = {}
for s in ss:
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1
print(sum(int((v * (v - 1)) / 2) for v in d.values() if v > 1))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
cdm = [_ for _ in range(a, b+1) if _%c != 0 and _%d != 0]

print(len(cdm))

### FIXED CODE ###

def lcm(a,b):
    ab = a*b
    while b != 0:
        a, b = b, a%b
    return ab //a

def su(n,c,d):
    return n - n//c - n//d + n//lcm(c,d)
    
def main():
    a,b,c,d = map(int,input().split())
    print(su(b,c,d) - su(a-1,c,d))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict

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

strList = defaultdict(list)

for leng in range(N // 2 + 1):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)


### FIXED CODE ###

from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
s.sort()

tt = [[],[]]
for i in s:
    if i not in tt[0]:
        tt[0] += [i]
        tt[1] += [1]
    else:
        idx = tt[0].index(i)
        tt[1][idx] += 1
t = tt
m = max(t[1])
ans = []
for i in range(len(t[1])):
    if t[1][i] == m:
        ans += [t[0][i]]

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

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
s.sort()

a = ""
tt = [[],[]]
for i in s:
    if a != i:
        a = i
        tt[0] += [i]
        tt[1] += [1]
    else:
        tt[1][-1] += 1
t = tt
m = max(t[1])
ans = []
for i in range(len(t[1])):
    if t[1][i] == m:
        ans += [t[0][i]]

for i in range(len(ans)): print(ans[i])
### BUGGY CODE ###

import sys

N, M = map(int,input().split())
a_lists = []

if N == 1:
    if M == 0:
        print (1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)
    
datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
else:
    datas[0]=1

if 1 in a_lists:
    datas[1] = 0
else:
    datas[1]= datas[0]+1
    
for i in range (2,N):
    if i in a_lists:
        datas[i] =0
    else:
        datas[i] = datas[i-1] + datas[i -2]

print(datas[-1]%1000000007)

### FIXED CODE ###

import sys
import heapq

N, M = map(int,input().split())
a_lists = []

if N == 1:
    if M == 0:
        print (1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)

a_lists.append(10**6)

datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
    heapq.heappop(a_lists) 
    
else:
    datas[0]=1

if 1 in a_lists:
    datas[1] = 0
    heapq.heappop(a_lists) 
else:
    datas[1]= datas[0]+1
    
heapq.heapify(a_lists)
    
for i in range (2,N):
    if i == a_lists[0]:
        datas[i] =0
        heapq.heappop(a_lists) 
    else:
        datas[i] = datas[i-1] + datas[i -2]

print(datas[-1]%1000000007)
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N = int(input())
    S = list(map(int, input().split()))
    tmp = [0, 0, 0]  # 皿パターン: 1,2,3個の寿司が置かれている皿の数
    for s in S:
        tmp[s-1] += 1
    d = defaultdict(int)
    d[tuple(tmp)] = 1

    e = 0  # 求める期待値
    X = sum(S)  # 残りの寿司の数
    while X > 0:
        A = d.items()
        d = defaultdict(int)
        for k, v in A:
            if k == (0, 0, 0):
                continue
            
            e += v / (sum(k)/N)  # 皿パターン数 * (寿司を食べられる期待値 := 寿司がある確率の逆数)

            if k[0] > 0:
                d[(k[0]-1, k[1], k[2])] += k[0] * v / sum(k)
            if k[1] > 0:
                d[(k[0]+1, k[1]-1, k[2])] += k[1] * v / sum(k)
            if k[2] > 0:
                d[(k[0], k[1]+1, k[2]-1)] += k[2] * v / sum(k)
        X -= 1

    print(e)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
# dp[i][j][k] := 寿司が 1 つある皿が i 皿、2 つが j 皿、
# 3 つが k 皿の状態から全て食べ終えるまでの操作回数の期待値
dp = [[[float(0)] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

a = list(map(int, input().split()))
I, J, K = a.count(1), a.count(2), a.count(3)

# 小さい方から dp を埋める
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if (i+j+k) <= N:
                # 式変形はググった…
                if (i+j+k) != 0:
                    dp[i][j][k] = float(N) / float(i+j+k)
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * float(i) / float(i+j+k)
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * float(j) / float(i+j+k)
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * float(k) / float(i+j+k)
print(dp[I][J][K])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from queue import Queue

N, M = [int(n) for n in input().split()]
graph = {n: [] for n in range(1, N+1)}
for m in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].append(B)
    graph[B].append(A)

starts_ = sorted(graph.keys(), key=lambda x: len(graph[x]))
starts = iter([starts_[n:n+1] for n in range(0, len(starts_), 1)])

result_path = []
for start in starts:
    q = Queue()
    #needs_start = graph[start]
    for s in start:
        q.put([s])
    while not q.empty():
        path = q.get()            
        for i, t in enumerate(graph[path[-1]]):
            if t in path:
                continue
            if len(set(graph[path[0]] + graph[t]) - set(path + [t])) == 0:
                result_path = path + [t]
                q = Queue()
                break
            else:
                if len(path + [t]) < N:
                    q.put(path+[t])
                break
                
    if len(result_path) > 0:
        break
print(len(result_path))
result = ""
for r in result_path:
    result += " {}".format(r)
print(result[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
def inpl(): return map(int, input().split())

N, M = inpl()
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

searched = [False] * (N+1)

m = 1
searched[m] = True

ans = []
def dfs(c):
    global ans
    searched[c] = True
    for d in G[c]:
        if not searched[d]:
            ans.append(c)
            dfs(d)
            break 
    else:
        ans.append(c)
    
dfs(1)
ans = ans[:0:-1]
dfs(1)

print(len(ans))
print(*ans)
### BUGGY CODE ###

N = int(input())
S = list(str(input()) for i in range(N))
 
Dic = {}
 
for s in S:
    if s in Dic:
        Dic[s] += 1
    else:
        Dic[s] = 1
 
for max_key in sorted([k for k, v in Dic.items() if v==max(Dic.values())]):
    print(max_key)

### FIXED CODE ###

import collections

n = int(input())
s = []
for i in range(n):
    s.append(input())

c = collections.Counter(s)
c_s = c.most_common()
m = c.most_common()[0][1]
ans = []
for j in range(len(c_s)):
    if c_s[j][1] != m:
        break
    else:
        ans.append(c_s[j][0])
ans.sort()
for t in ans:
    print(t)
### BUGGY CODE ###

import sys
import numpy as np

N = int(input())

a = np.zeros((100, 100, 100), dtype=np.int32)


for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            n = int(i*i + j*j + k*k + i*j + j*k + k*i)
            a[i,j,k] = n

            if n > 1001:
                break
for i in range(N):

    print(np.count_nonzero(a == (i+1)))



### FIXED CODE ###

import sys
import numpy as np

N = int(input())

o = [0] * (N+1)
for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            n = int( ((i+j) * (j+k)) + i*i + k*k)
            if n < (N+1):
                o[n] += 1
            if n > 10001:
                break

for i in range(N):
    print(o[i+1])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

### FIXED CODE ###

from collections import defaultdict
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort(key=itemgetter(0))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)
### BUGGY CODE ###

# edpc e dp

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0 for j in range(W + 1)] for i in range(N)]
for i in range(W + 1):
    if i == w[0]:
        dp[0][i] = v[0]
    else:
        dp[0][i] = 0
for i in range(1, N):
    for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
print(dp[-1][-1])


### FIXED CODE ###

# edpc e dp

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0 for j in range(W + 1)] for i in range(N)]
for i in range(W + 1):
    if i == w[0]:
        dp[0][i] = v[0]
    else:
        dp[0][i] = 0
for i in range(1, N):
    for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
ans = -INF
for i in range(W + 1):
    ans = max(ans, dp[-1][i])
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])
       


### FIXED CODE ###

N,W=map(int,input().split())
taple=[]
for i in range(N):
    w,v=map(int,input().split())
    taple.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=taple[i-1]
    for j in range(N*(10**3)+1):
        if j>=v:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break