Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10
#solve


def solve():
    n, m = LI()
    a = LI()
    bi = 0
    while not (a[0] & 1):
        bi += 1
        a[0] = a[0] >> 1
    for ai in a[1:]:
        tmp = 0
        while not (ai & 1):
            tmp += 1
            ai = ai >> 1
        if tmp == bi:
            continue
        print(0)
        return

    def lcm(a):
        from fractions import gcd
        x = a[0]
        for i in range(1, len(a)):
            x = (x * a[i]) // gcd(x, a[i])
        return x
    lc = lcm(list(map(lambda x: x >> 1 : set(a))))
    print((m + lc) // lc // 2)
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    k, x = LI()
    if k * 500 >= x:
        print("Yes")
    else:
        print("No")
    return


#main
if __name__ == '__main__':
    solve()
n = int(input())
lst = list(map(int,input().split()))

lst = sorted(lst)
bol = [True]*n
s=0
for i in range(n-1):
  if bol[i] == True:
    bol[i] = False
    if lst[i] != lst[i+1]:
      s += 1
    
    for j in range(i+1,n):
      if bol[j] == True and lst[j] % lst[i] == 0:
        bol[j] = False

if bol[n-1] == True:
  s += 1
  
print(s)  


### FIXED CODE ###

lst = list(map(int,input().split()))

for x in lst:
  if x == 0:
    s = lst.index(x) + 1
    
print(s)
a, b, k = map(int, input().split())

num = list(range(a, b + 1))

a_k = num[:k]
k_e = num[-k:]

# print(a_k, k_e)
ans_set = set(a_k) | set(k_e)
for i in sorted(list(ans_set)):
    print(i)


### FIXED CODE ###

a,b,k=map(int,input().split())
r=range(a,b+1)
for i in sorted(set(r[:k])|set(r[-k:])):
  print(i)
def calc(x):
    return (x+1)/2

n, k = map(int, input().split())
p = list(map(calc,(map(int, input().split()))))

_ans = sum(p[0:k])
ans = _ans
for x in range(n-k+1):
    _ans = _ans - p[x] + p[k]
    ans = max(ans, _ans)

print(ans)


### FIXED CODE ###

def calc(x):
    return (x+1)/2

n, k = map(int, input().split())
p = list(map(calc,(map(int, input().split()))))

_ans = sum(p[0:k])
ans = _ans
for x in range(n-k):
    # print(x, x + k)
    _ans = _ans - p[x] + p[x + k]
    ans = max(ans, _ans)

print(ans)
n = int(input())
a = list(map(int, input().split(' ')))
if a.index(0) >= 0:
	print(0)
else:
	lim = int(1e18)
	mult = 1
	for v in a:
		if mult > lim:
			break
		else:
			mult *= v
	if mult > lim:
		print("-1")
	else:
		print(mult)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
if a.count(0) > 0:
	print("0")
else:
	lim = int(1e18)
	mult = 1
	for v in a:
		if mult > lim:
			break
		else:
			mult *= v
	if mult > lim:
		print("-1")
	else:
		print(mult)
import numpy as np

H, W = map(int, input().split())
A = [np.array(list(map(int, input().split()))).astype("int64") for _ in range(H)]

odds = []
for i in range(H):
    for j in range(W):
        if A[i][j]%2!=0:
            odds.append([i+1, j+1])

diff = []
for k in range(len(odds)//2):
    d_x = odds[2*k+1][0]-odds[2*k][0]
    d_y = odds[2*k+1][1]-odds[2*k][1]
    diff.append([d_x, d_y])

odds = np.array(odds)
diff = np.array(diff)

N = sum(sum(diff))

print(N)

for i in range(len(odds)//2):
    j = 0
    k = 0
    temp = odds[2*i]
    if diff[i][0]!=0:
        x_unit = (diff[i]-diff[i][1]*np.array([0, 1]))//diff[i][0]
        while j<diff[i][0]:
            print(temp[0], temp[1], (temp+x_unit)[0], temp[1])
            temp += x_unit
            j+=1
    if diff[i][1]!=0:
        y_unit = (diff[i]-diff[i][0]*np.array([1, 0]))//diff[i][1]
        while k<diff[i][1]:
            print(temp[0], temp[1], temp[0], (temp+y_unit)[1])
            temp += y_unit
            k+=1

### FIXED CODE ###

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

arr = []
for i in range(H-1):
    for j in range(W):
        if A[i][j]%2!=0:
            A[i+1][j]+=1
            arr.append([i+1, j+1, i+2, j+1])
            
for k in range(W-1):
    if A[H-1][k]%2!=0:
        A[H-1][k+1]+=1
        arr.append([H, k+1, H, k+2])
        
N = len(arr)

print(N)

for i in range(N): 
    print(arr[i][0], arr[i][1], arr[i][2], arr[i][3])
import math

N=int(input())
A=list(map(int,input().split()))

ans=0
for i in range(N-1):
    tmp = A[i]-A[i+1]
    if tmp <=0:
        ans = ans + tmp
        A[i+1] = A[i]

Print(ans)


### FIXED CODE ###

import math

N=int(input())
A=list(map(int,input().split()))

ans=0
for i in range(N-1):
    tmp = A[i]-A[i+1]
    if tmp >=0:
        ans = ans + tmp
        A[i+1] = A[i]

print(ans)
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

graph = {i: [] for i in range(1, m + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

print("Yes")
for i in range(2, n + 1):
    print(sirube[i])

### FIXED CODE ###

import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

print("Yes")
for i in range(2, n + 1):
    print(sirube[i])
N = int(input())
a = list(map(int,input().split()))
one = 0
four = 0
two = 0

for j in range(N):

  if a[j]%2 == 1:
    one += 1
  elif a[j]%4 == 0:
    four += 1
  else :
    two +=1

  
if one =< four:
  print('Yes')
else :
  if two == 0 and four == one -1:
     print('Yes')
  else:
    print('No')

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
one = 0
four = 0
two = 0

for j in range(N):

  if a[j]%2 == 1:
    one += 1
  elif a[j]%4 == 0:
    four += 1
  else :
    two +=1

print("Yes" if four >= one or (four == one - 1 and two == 0) else "No")
H, W, K = map(int, input().split())
fi = []
for _ in range(H):
  s = input()
  fi.append(s)
a = 1 << H
b = 1 << W
total = 0

for i in range(a * b):
  lh = list()
  lw = list()

  for j in range(h):
    if i & (1 << j):
      lh.append(1)
    else:
      lh.append(0)
  for j in range(W):
    if i & (1 << (j + H)):
      lw.append(1)
    else:
      lw.append(0)

  cnt = 0
  for j in range(H):
    for l in range(W):
      if lh[j] == 1 or lw[j] == 1:
        continue
      if fi[j][l] == '#':
        cnt += 1
  if cnt == K:
    total += 1

print(total)


### FIXED CODE ###

H, W, K = map(int, input().split())
fi = []
for _ in range(H):
    s = input()
    fi.append(s)
a = 2 ** H
b = 2 ** W
total = 0

for i in range(a * b):
    lh = list()
    lw = list()

    for j in range(H):
        if i & (1 << j):
            lh.append(1)
        else:
            lh.append(0)
    for j in range(W):
        if i & (1 << (j + H)):
            lw.append(1)
        else:
            lw.append(0)
    # print(lh)
    # print(lw)

    cnt = 0
    for j in range(H):
        for l in range(W):
            if lh[j] == 1 or lw[l] == 1:
                continue
            if fi[j][l] == '#':
                cnt += 1
    # print(cnt)
    if cnt == K:
        total += 1

print(total)
n,y=map(int,input())
for i in range(n):
  for j in range(i,n):
    k=n-i-j
    if i*10000+j*5000+k*1000==y:
      print(i,j,k)
      exit()
print(-1,-1,-1)


### FIXED CODE ###

n,y=map(int,input().split())
for i in range(n+1):
  for j in range(n+1-i):
    k=n-i-j
    if i*10000+j*5000+k*1000==y:
      print(i,j,k)
      exit()
print(-1,-1,-1)
print('second' if all(a[i] % 2 == 0 for i in range(N)) else 'first')

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
print('second' if all(a[i] % 2 == 0 for i in range(n)) else 'first')
n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]

a.sort()
a.reverse()

ans="Yes"
for i in range(m):
    if a[i]<sum(a)/(4*m):
        ans="No"
        break;
print(ans)

### FIXED CODE ###

a,b,c=[int(x) for x in input().split()]

print(c,a,b)
D, G = [int(n) for n in input().split()]

score_table = []
for i in range(1, D+1):
    p, c = [int(n) for n in input().split()]
    score_table.append([i*100, p, c])

min_count = sum([l[1] for l in score_table])
#print(min_count)

for bit in range(1<<D):
    score = 0
    count = 0

    for i in range(D):
        if bit & (1<<i):
            score += score_table[i][0] * score_table[i][1] + score_table[i][2]
            count += score_table[i][1]
    
    if score >= G:
        min_count = min(min_count, count)
    else:
        additional = []
        for j in range(D):
            if not bit & (1<<j):
                additional.append(score_table[j])
        
        additional_ = sorted(additional, key=lambda x:x[0], reverse=True)
        #print(additional_)
        
        for i in additional_:
            if i[1] > 1:
                add_score = i
                break
        
        for k in range(1, add_score[1]):
            score += add_score[0]
            count += 1
            if score >= G:
                min_count = min(min_count, count)

print(min_count)

### FIXED CODE ###

D, G = [int(n) for n in input().split()]

score_table = []
for i in range(1, D+1):
    p, c = [int(n) for n in input().split()]
    score_table.append([i*100, p, c])

min_count = sum([l[1] for l in score_table])
#print(min_count)

for bit in range(1<<D):
    score = 0
    count = 0

    for i in range(D):
        if bit & (1<<i):
            score += score_table[i][0] * score_table[i][1] + score_table[i][2]
            count += score_table[i][1]
    
    if score >= G:
        min_count = min(min_count, count)
    else:
        additional = []
        for j in range(D):
            if not bit & (1<<j):
                additional.append(score_table[j])
        
        additional_ = sorted(additional, key=lambda x:x[0], reverse=True)
        #print(additional_)
        
        # for i in additional_:
        #     if i[1] > 1:
        #         add_score = i
        #         break

        add_score = additional_[0]

        for k in range(add_score[1]-1):
            score += add_score[0]
            count += 1
            if score >= G:
                min_count = min(min_count, count)

print(min_count)
a,b=map(int,input().split())
print((a//2)*((a+1)//2))

### FIXED CODE ###

a=int(input())
print((a//2)*((a+1)//2))
a, b = map(int, input().split())
v = (a + b) // 2
if abs(a - v) == abs(b - v)
    print(v)
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

a, b = map(int, input().split())
v = (a + b) // 2
if abs(a - v) == abs(b - v):
    print(v)
else:
    print('IMPOSSIBLE')
x=int(input())
for i in range(100):
    k=x-i**5
    a=k**0.2
    if type(a)==complex:
        continue
    if a.is_integer():
        break
print(-i,int(a))

### FIXED CODE ###

s=input()
if s=="ABC":
    print("ARC")
else :
    print("ABC")
N, M=map(int, input().split())
for n in range(N):
 arr = list(map(int, input().split()))
 sum = sum(arr)
 print(" ".join(arr) + " " + sum)

### FIXED CODE ###

N, M=map(int, input().split())
s_row = [0 for x in range(M+1)]
for n in range(N):
 arr = list(map(int, input().split()))
 arr.append(sum(arr))
 s_row = [x+y for x,y in zip(s_row, arr)]
 print(" ".join([str(x) for x in arr]))
print(" ".join([str(x) for x in s_row]))
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(2,n+1):
    for j in range(n-i+1):
        k=j+i-1 
        dp[j][k]=max(a[k]-dp[j][k-1],a[j]-dp[j+1][k])
print(dp[0][len(a)-1])

### FIXED CODE ###

import sys
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(2,n+1):
    for j in range(n-i+1):
        k=j+i-1 
        dp[j][k]=max(a[k]-dp[j][k-1],a[j]-dp[j+1][k])
print(dp[0][len(a)-1])
N,K = map(int,input().split())
H = list(map(int,input().split()))
H.sort()
ans = K
for i in range(K):
    H.pop()
ans += sum(H)

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
H.sort()
ans = 0
for i in range(min(K,N)):
    H.pop()
ans += sum(H)
print(ans)
N,A = map(int,input().split())
X = list(map(int,input().split()))

ma = max(X)

dp = [[[0 for s in range(N*ma+1)] for k in range(N+1)] for j in range(N+1)]

dp[0][0][0] = 1

for j in range(1,N+1) :
    for k in range(N+1) :
        for s in range(N*ma+1) :
            if (j >= 1) and (s < X[j-1]) :
                dp[j][k][s] = dp[j-1][k][s]
            elif (j >= 1) and (k >= 1) and (s >= X[j-1]) :
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
            else :
                dp[j][k][s] = 0

ans = 0

for k in range(1,N+1) :
    ans += dp[N][k][k*A]

print(ans)


### FIXED CODE ###

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

X = list(map(int,input().split()))

ma = max(X)

dp = [[[0 for s in range(ma*N+1)] for k in range(N+1)] for i in range(N+1)]

dp[0][0][0] = 1

for i in range(1,N+1) :
    for k in range(i+1) :
        for s in range(ma*N+1) :
            if (k >= 1) and (s >= X[i-1]) :
                dp[i][k][s] = dp[i-1][k][s] + dp[i-1][k-1][s-X[i-1]]
            else :
                dp[i][k][s] = dp[i-1][k][s]

ans = 0

for k in range(1,N+1) :
    if k*A > ma*N :
        break
    ans += dp[N][k][k*A]

print(ans)
N=int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

for i in range(N):
  if i%2==1:
    S+=a[i]
  else:
    S-=a[i]
print(S)

### FIXED CODE ###

N=int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
S=0
for i in range(N):
  if i%2==0:
    S+=a[i]
  else:
    S-=a[i]
print(S)
a,b = map(int, input(),split())
c = (a-1) * (b-1)
print(c)

### FIXED CODE ###

a,b=map(int, input().split())
c=(a-1)*(b-1)
print(c)
hoge=input()
no=0
if(hoge[0]=="A"):
  hoge.strip("A")
else:
  no=1

if(hoge[0].islower()):
  hoge.strip(hoge[0])
else:
  no=1

if(hoge[0]=="C"):
  hoge.strip("C")
else:
  no=1
  
if(hoge.islower()==false):
  no=1
  
if(no==0):
  print("AC")
else:
  print("WA")

### FIXED CODE ###

#ABC097B
hoge=input()
no=0

if(hoge[0]=="A"):
    hoge=hoge.replace("A","a",1)
else:
    no=1
    
if not(hoge[1].islower() and hoge[-1].islower()):
    no=1

if(hoge.count("C")==1):
    hoge=hoge.replace("C","c",1)
else:
    no=1
    
if(hoge.islower() and no==0):
    print("AC")
else:
    print("WA")
x=int(input())
ans=0
for i in range(1,32):
  for j in range(2,10):
    if x>=i**j:
      ans=(max(ans,i**J))
print(ans)

### FIXED CODE ###

x=int(input())
ans=0
for i in range(1,32):
  for j in range(2,10):
    if x>=i**j:
      ans=(max(ans,i**j))
print(ans)
newArray = []
 
x = input()
 
while x != "0":    
    newArray.append(x)
    x = input()
 
for i in range(len(newArray)):
    print("Case {}:{}".format((str(i + 1)),(newArray[i]))

### FIXED CODE ###

x=int(input())
i=1
while x!=0:
    print("Case %d: %s" %(i,x))
    x=int(input())
    i+=1
S=input()
T=input()
 
if S==T:
    ans="Yes"
else:
    ans="No"
    for _ in range(len(S)):
        rotated_S=S[len(S)-1:]+S[:len(S)-1]
        if rotated_S==T:
            ans="Yes"
            break
        else:
            S=rotated_S
print(ans)

### FIXED CODE ###

A= list(map(int, input().split()))
B= sorted(A)
print(B[2]-B[0])
h,m,s=int(int,raw_input().split())
print 3600*h+60*m+s

### FIXED CODE ###

s=int(raw_input())
h=s/3600
m=(s-3600*h)/60
print "%d:%d:%d"%(h,m,s-3600*h-60*m)
W, a, b = map(int, input().split())
print(max(0, abs(A - B) - W))

### FIXED CODE ###

W, a, b = map(int, input().split())
print(max(0, abs(a - b) - W))
N = int(input())
G = [[] for _ in range(N)]

def dfs(v, dist):
  for nv, e_dist in G[v]:
    if ans[nv] == -1:
      ans[nv] = (dist + e_dist) % 2
      dfs(nv, dist + e_dist)

for i in range(N-1):
  u, v, w = map(int, input().split())
  G[u-1].append([v-1, w])
  G[v-1].append([u-1, w])

ans = [-1] * N
dfs(0, 0)

print(*ans, sep="\n")

### FIXED CODE ###

import sys
sys.setrecursionlimit(pow(10, 9))

N = int(input())
G = [[] for _ in range(N)]

def dfs(v, dist):
  for nv, e_dist in G[v]:
    if ans[nv] == -1:
      ans[nv] = (dist + e_dist) % 2
      dfs(nv, dist + e_dist)

for i in range(N-1):
  u, v, w = map(int, input().split())
  G[u-1].append([v-1, w])
  G[v-1].append([u-1, w])

ans = [-1] * N
dfs(0, 0)

print(*ans, sep="\n")
n = int(input())
num = list(map(int, input().split()))
limit = 10**18
 
num.sort()
result = A[0]
 
for i in num[1:]:
    result *= i
    if result > limit:
        exit()
        
print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c　= (a * b) % 2
if c == 1:
  print("Odd")
else:
  print("Even")


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = (a * b) % 2
if c == 0:
  print("Even")
else :
  print("Odd")
N=int(input())
s=input()

#毎ステップ毎にカウントする処理→TLE
# ans=10**6
# for i in range(1,N):
#   ans=min(ans,s[:i-1].count("W")+s[i+1:].count("E"))
# print(ans)
ans=[]
ans.append(s[1:].count("E"))
tmp=ans[0]
for i in range(1:N):
  if s[i]=="E":
    tmp-=1
  if s[i-1]=="W":
    tmp+=1
  ans.append(tmp)
print(min(ans))

### FIXED CODE ###

n=int(input())
s=input()

#毎ステップ毎にカウントする処理→TLE
# ans=10**6
# for i in range(1,N):
#   ans=min(ans,s[:i-1].count("W")+s[i+1:].count("E"))
# print(ans)
ans=[]
ans.append(s[1:].count("E"))
tmp=ans[0]
for i in range(1,n):
  if s[i]=="E":
    tmp-=1
  if s[i-1]=="W":
    tmp+=1
  ans.append(tmp)
print(min(ans))
import sys

sys.setrecursionlimit(2000)

n = int(input())

p = [[] for i in range(n)]

for i in range(n-1):
    u, v, w = list(map(int, input().split()))
    u = u-1
    v = v-1
    p[u].append((v, w))
    p[v].append((u, w))

c = [-1 for i in range(n)]

def dfs(num, zo):
    if c[num] != -1:
        return
    else:
        c[num] = zo
    for v, w in p[num]:
        if w % 2 == 0:
            dfs(v, zo)
        else:
            dfs(v, not zo)
dfs(0, 0)

for i in range(n):
    print(1 if c[i] else 0)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**5)

n = int(input())

p = [[] for i in range(n)]

for i in range(n-1):
    u, v, w = list(map(int, input().split()))
    u = u-1
    v = v-1
    p[u].append((v, w))
    p[v].append((u, w))

c = [-1 for i in range(n)]

def dfs(num, zo):
    if c[num] != -1:
        return
    else:
        c[num] = zo
    for v, w in p[num]:
        if w % 2 == 0:
            dfs(v, zo)
        else:
            dfs(v, not zo)
dfs(0, 0)

for i in range(n):
    print(1 if c[i] else 0)
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)

import numpy as np
# 流れ
# dpテーブルのサイズを決める
#     (N,max(V)*N)
# dpテーブルの初期化
# dpテーブルの更新
#     いままでと同じ
#     sum_v以上を達成すhるように選んだときのsum_wの最小値を保持する
# 答えの抽出
# dpでW以下かつ最大価値が最大(sum_v)なものが答え


dp = np.full((N+1, np.max(V) * N+1), float('inf'))
# dp[:, 0] = 0
dp[0][0] = 0

from itertools import product

for i, sum_v in product(range(N), range(np.max(V) * N+1)):
    if sum_v - V[i] < 0:
        dp[i + 1, sum_v] = dp[i, sum_v]
    else:
        # print(i, sum_v)
        dp[i + 1, sum_v] = min(
            dp[i, sum_v],
            dp[i, sum_v-V[i]]+W[i]
        )

# print(dp)
print(np.where((dp <= K).sum(axis=0) != 0)[0].max())
# print(max(np.where((dp < K).sum(axis=0) != 0)))
# print(max(np.where((dp < K).sum(axis=0) != 0)))


### FIXED CODE ###

import sys
read = sys.stdin.readline


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


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE