Harryxun/stf_run huggingface dataset:
import copy

H, W = map(int, input().split())

def fib(msLst, i, j):
    if i > 0:
        msLst[i - 1][j] = '#'
    if i < W - 1:
        msLst[i + 1][j] = '#'
    if j > 0:
        msLst[i][j - 1] = '#'
    if j < H - 1:
        msLst[i][j + 1] = '#'

ansCnt = 0
masLst = [['' for i in range(H)] for j in range(W)]
for i in range(W):
    tmp = input()
    for j in range(len(tmp)):
        masLst[i][j] = tmp[j]

loopBoean = True

while loopBoean:
    jloop = True
    tmp = 0
    msLst = copy.deepcopy(masLst)
    for i in range(W):
        for j in range(H):
            if masLst[i][j] == '#':
                fib(msLst, i, j)
            if masLst[i][j] == '.':
                if tmp == 0:
                    tmp = 1
            if msLst[i][j] != '#':
                jloop = False
    masLst = msLst
    if tmp == 1:
        ansCnt += tmp

    if jloop == True:
        loopBoean = False

print(ansCnt)

### FIXED CODE ###

from collections import deque

def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[p[0]][p[1]] + 1
                que.append([nextX, nextY])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

que = deque()
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            que.append([i, j])
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)
s=input()
q=int(input())
from collections import deque
qq=deque(s)
cnt=0
for i in range(q):
    j=input()
    if j=="1":
        cnt+=1
        continue
    _,k,l=j.split()
    if (k=="2")^cnt%2:
        qq.append(l)
    else:
        qq.appendleft(l)

if cnt%2==1:
    print("".join(revesed(list(qq))))
else:
    print("".join(qq))

### FIXED CODE ###

s=input()
q=int(input())
from collections import deque
qq=deque(s)
cnt=0
for i in range(q):
    j=input()
    if j=="1":
        cnt+=1
        continue
    _,k,l=j.split()
    if (k=="2")^cnt%2:
        qq.append(l)
    else:
        qq.appendleft(l)

if cnt%2==1:
    print("".join(reversed(list(qq))))
else:
    print("".join(qq))
def col(i):
    for x in G[i]:
        v,w = x[0],x[1]
        if hist[v]==0:
            if w%2==0:
                C[v]=C[i]
            else:
                C[v]=1-C[i]
            hist[v] = 1
            col(v)
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    u,v,w = map(int,input().split())
    G[u].append((v,w))
    G[v].append((u,w))
C = {i:0 for i in range(1,N+1)}
hist = [0 for i in range(N+1)]
hist[1] = 1
col(1)
for i in range(1,N+1):
    print(C[i])

### FIXED CODE ###

from collections import deque
N = int(input())
G = {}
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if u not in G:
        G[u] = []
    G[u].append((v,w%2))
    if v not in G:
        G[v] = []
    G[v].append((u,w%2))
que = deque([(1,0)])
hist = [0 for _ in range(N+1)]
hist[1] = 1
col = [0 for _ in range(N+1)]
while que:
    u,c = que.popleft()
    for x in G[u]:
        v,w = x[0],x[1]
        if hist[v]==0:
            if w==0:
                col[v] = c
                que.append((v,c))
            else:
                col[v] = 1-c
                que.append((v,1-c))
            hist[v] = 1
for i in range(1,N+1):
    print(col[i])
# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.values())

rewrite = 0
l = len(soretedList)

while l > K:
    head = soretedList.pop(0)
    rewrite += head
    
print(rewrite)

    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.values())

l = len(soretedList)

if len(soretedList) <= K :
    print(0)
else:
    print(N - sum(soretedList[l-K:] ))
for i in range(2):
    S, W = [int(x) for x in input().split()]
if W >= S:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

a,b=map(int,input().split(' '))
if(a>b):
    print('safe')
else:
    print('unsafe')
import numpy as np

a, b = map(int, input().split())

print(np.lcm(a, b))


### FIXED CODE ###

a, b = map(int, input().split())


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def lcm(x, y):
    return (x * y) // gcd(x, y)


print(lcm(a, b))
import sys
sys.setrecursionlimit(100000)

def main():
    n = int(input())
    data = list(map(int, input().split()))

    if n == 1:
        print(data[0])
    elif n == 2:
        print(data[1], data[0])
    else:
        firs_value = [data[0]]
        second_value = [data[1], data[0]]

        def get_value(index, data):
            if index == 0:
                return firs_value
            elif index == 1:
                return second_value
            else:
                lis = get_value(index - 2, data)
                lis.append(data[index - 1])
                lis.insert(0, data[index])
                return lis

        result = get_value(n - 1, data)
        print(" ".join(str(n) for n in result))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    data = list(map(int, input().split()))

    if n == 1:
        print(data[0])
    else:
        result = [None] * n

        if n % 2 == 0:
            center = int(n / 2)
            for index, value in enumerate(data):
                if index % 2 == 0:
                    result[center + int(index / 2)] = value
                else:
                    result[center - int((index + 1) / 2)] = value
            print(" ".join(str(n) for n in result))
        else:
            center = int(n / 2)
            for index, value in enumerate(data):
                if index % 2 == 0:
                    result[center - int(index / 2)] = value
                else:
                    result[center + int((index + 1) / 2)] = value
            print(" ".join(str(n) for n in result))

if __name__ == '__main__':
    main()
n = int(input())
t, a = map(int, input().split())
li = list(map(int, input().split()))
x = 55
ind = 0
for i in li:
    mean = t - li[i] * 0.006
    sa = abs(mean - a)
    if sa < x:
        x = sa
        ind = i + 1
print(ind)

### FIXED CODE ###

n = int(input())
t, a = map(int, input().split())
li = list(map(int, input().split()))
x = 10**9
ind = 0
for i in range(n):
    mean = t - li[i] * 0.006
    sa = abs(mean - a)
    if sa < x:
        x = sa
        ind = i + 1
print(ind)
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
N = int(input())
ab = [chr(ord('a') + i) for i in range(26)]
j = 1
while True:
  temp = 1000000000000001//(26**j)
  j+=1
  if temp<1:
    break
ans = ''
for i in range(1, j+2):
  ax = (N//(26**(i-1)))%26
  if ax==0:
    ax = 25
  ans += ab[ax]
  if N//(26**i)<1:
    print(ans[::-1])
    sys.exit()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
a = str(input())
if a.isupper():
  print('A')
else:
  print('a')
a=input().sprit()
ans=0
if a[1]-1a[0]>=1:
  ans+=a[1]*2-1
elif a[0]-a[1]>=1:
  ans+=a[0]*2-1
else:
  ans+=a[0]+a[1]
print(ans)
  

### FIXED CODE ###

b=input().split(" ")
a=[]
for i in b:
  a+=[int(i)]
ans=0
if a[1]-a[0]>=1:
  ans+=a[1]*2-1
elif a[0]-a[1]>=1:
  ans+=a[0]*2-1
else:
  ans+=a[0]+a[1]
print(ans)
ans = ''
if first * last > 0:
    ans = 0
elif (abs(last) == 0):
    ans = 'infinity'
elif abs(first) * 2 < abs(second):
    ans = 1
else:
    if abs(first) % abs(last) == 0:
        ans = (abs(first) // abs(last)) * 2
    elif abs(first) * 2 == abs(last):
        ans = 2
    else:
        ans = math.floor(2 * abs(first) / abs(last))

### FIXED CODE ###

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
first = a1 * t1 - b1 * t1
second = (a2 * t2 - b2 * t2)
last = second + first
if first * last > 0:
    ans = 0
elif (abs(last) == 0):
    ans = 'infinity'
else:
    s = abs(first) // abs(last)
    t = abs(first) % abs(last)
    ans = 2 * s
    if t != 0:
        ans += 1
print(ans)
a=[]
for _ in range(4):
	a.append(int(input())

print(min(a[0],a[1])+min(a[2],a[3]))

### FIXED CODE ###

a=[]
for _ in range(4):
	a.append(int(input()))

print(min(a[0],a[1])+min(a[2],a[3]))
import sys

q=input()
x=[int(i) for i in input().split()]
cnt=input()
j=0
y=[int(i) for i in input().split()]

z=[0]*max(x)

for k in x :
    z[k] += 1
    
for i in y :
    z[i] -= 1
    if z[i] == -1 :
        print('NO')
        sys.exit()
print('YES')


### FIXED CODE ###


q=input()
x=[int(i) for i in input().split()]
cnt=input()
y=[int(i) for i in input().split()]

if max(x) >= max(y):
    MAX=max(x)
else:
    MAX=max(y)

dic = {}

for k in x :
    if k in dic.keys() :
        dic[k] += 1
    else :
        dic[k] = 1
    
for i in y :
    if i in dic.keys() :
        dic[i] -= 1
        if dic[i] == -1 :
            print('NO')
            exit()
    else :
        print('NO')
        exit()
print('YES')
n, r = map(int, input().split())

if n >= 10:
  print(R)
else:
  print(r +  100 * (10 - n))

### FIXED CODE ###

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

if n >= 10:
  print(r)
else:
  print(r +  100 * (10 - n))
N = int(input())
S = input()

if N % 2 == 0:
  str = S[:N/2+1]
  strstr = str + str
  if S == str:
      print("Yes")
  else:
      print("No")
else:
  print("No")

### FIXED CODE ###

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

if N % 2 == 0:
    num = int(N/2)
    string = S[:num]
    strstr = string + string
    if S == strstr:
        print("Yes")
    else:
        print("No")
else:
    print("No")
M1,D1=map(int,input.split())
M2,D2=map(int,input.split())

if d2==1:
  print 1
else:
  print 0

### FIXED CODE ###

M1, D1 = map(int, input().split())
M2, D2 = map(int, input().split())

if D2 == 1:
    print(1)
else:
    print(0)
n = int(input())
A= map(int,input().split())
for i in range(n):
    if(A[i]%2==0):
        if(A[i]%5!=0 or A[i]%3!=0):
            print("DENIED")
            exit()
print("APPROVED")


### FIXED CODE ###

n = int(input())
A=list(map(int,input().split()))
for i in range(n):
    if(A[i]%2==0):
        if(A[i]%5!=0 and A[i]%3!=0):
            print("DENIED")
            exit()
print("APPROVED")
n = int(input().rstrip())
a = int(input().rstrip())
b = int(input().rstrip())

if n == 1:
    print("Hello World")
else:
    print(a+b)


### FIXED CODE ###

n = int(input().rstrip())
if n == 1:
    print("Hello World")
else:
    a = int(input().rstrip())
    b = int(input().rstrip())
    print(a+b)
import numpy as np
N,K=input().split()
N=int(N)
K=int(K)

A=list(map(int, input().split()))
A=np.array(A)
sort_A=np.sort(A)[::-1]
sort_A=sort_A[K:]

print(np.sum(sort_A))

### FIXED CODE ###

H,A=input().split()
H=int(H)
A=int(A)

count=0
while H>0:
  H=H-A
  count+=1
print(count)
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cou = 0
for j,k in zip(a,b):
  if j<k:
    cou += (k-j)//2
  elif j>k:
    cou -= (j-k)
if cou>=0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x,y = map(int,input().split())
if x % y ==0:
  print(-1)
else:
  print(x)
import sys
from itertools import product
input = sys.stdin.readline
xyh = []
xyh0 = []
N=int(input())
for _ in range(N):
    tmp1, tmp2, tmp3 = map(int, input().split())
    if tmp3 > 0:
        xyh.append((tmp1, tmp2, tmp3))
    else:
        xyh0.append((tmp1, tmp2, tmp3))
ans = None
for cx, cy in product(range(101), repeat=2):
    H = None
    H_lower = 1
    is_ok = 1
    for x, y, h in xyh:
        if H is None:
            H = abs(x-cx)+abs(y-cy)+h
        else:
            if H != abs(x-cx)+abs(y-cy)+h:
                is_ok = 0
                break
    if not is_ok or H is None:
        continue
    for x, y, h in xyh0:
        H_lower = max(H_lower, abs(x-cx)+abs(y-cy))
    if H < H_lower:
        continue
    ans = (cx, cy, H)
    break
        
print(*ans)

### FIXED CODE ###

from itertools import product
xyh = []
xyh0 = []
N=int(input())
for _ in range(N):
    tmp1, tmp2, tmp3 = map(int, input().split())
    if tmp3 > 0:
        xyh.append((tmp1, tmp2, tmp3))
    else:
        xyh0.append((tmp1, tmp2, tmp3))
ans = None
for cx, cy in product(range(101), repeat=2):
    H = None
    H_lower = 1
    H_upper = 10**100
    is_ok = 1
    for x, y, h in xyh:
        if H is None:
            H = abs(x-cx)+abs(y-cy)+h
        else:
            if H != abs(x-cx)+abs(y-cy)+h:
                is_ok = 0
                break
    if not is_ok or H is None:
        continue
    for x, y, h in xyh0:
        H_upper = min(H_upper, abs(x-cx)+abs(y-cy))
    if H > H_upper or H < H_lower:
        continue
    ans = (cx, cy, H)
    break

print(*ans)
S = list(input())
L = len(S)
Slist = set()
for i in range(L):
    Slist.add(ord(S[i]))
Slist = list(Slist)
Slist.sort()
ans = "None"
j = 0
for i in range(97, 123):
    if Slist[j] == i:
        j += 1
        continue
    ans = chr(i)
    break
print(ans)


### FIXED CODE ###

S = list(input())
L = len(S)
Slist = set()
for i in range(L):
    Slist.add(ord(S[i]))
Slist = list(Slist)
Slist.sort()
ans = "None"
j = 0
L = len(Slist)
for i in range(97, 123):
    if Slist[j] == i:
        j += 1
        if j >= L and i+1 < 123:
            ans = chr(i+1)
            break
        continue
    ans = chr(i)
    break
print(ans)
# import pandas as pd
import numpy as np


N = int(input())
keihin = []
for i in range(N):
    keihin.append(input())

nn = np.array(keihin)


print(np.unique(nn).size)








### FIXED CODE ###

a = input().split()
S = int(a[0])
W = int(a[1])
if S <= W:
    print("unsafe")
else:
    print("safe")
import numpy as np
tmp=[int(i) for i in input().split(' ')]
tmp_s=np.array([int(i) for i in input().split(' ')])
score=np.zeros(tmp[0]-tmp[1]+1)
for i in range(tmp[0]-tmp[1]+1):
  if i==0:
    score[0]=np.prod(tmp_s[:tmp[1]])
  else:
    if tmp_s[i-1]==0:
      score[i]=np.prod(tmp_s[i:i+tmp[1]-1])
    else:
      score[i]=tmp_s[i+tmp[1]-1]*score[i-1]/tmp_s[i-1]
    
    if score[i-1]<score[i]:
      print('Yes')
    else:
      print('No')

### FIXED CODE ###

X=int(input())
if X>=400 and X<=599:
  print(8)
elif X>=600 and X<=799:
  print(7)
elif X>=800 and X<=999:
  print(6)
elif X>=1000 and X<=1199:
  print(5)
elif X>=1200 and X<=1399:
  print(4)
elif X>=1400 and X<=1599:
  print(3)
elif X>=1600 and X<=1799:
  print(2)
elif X>=1800 and X<=1999:
  print(1)
import sys

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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt = ""
    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    while lt != 0 or ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt + s[ls]

    print(txt[::-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math


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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt=""
    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    while lt != 0 and ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt +s[ls]

    print(txt[::-1])


if __name__ == "__main__":
    main()
n = input()
_list = input().split(" ")
_list = [int(x) for x in _list]
even = [x for x in _list if x % 2 == 0]
answer = []
for x in even:
    if x % 3 == 0 or x % 5 == 0:
        answer.append(True)
if len(even) == len(answer):
    print("APPROVED")
else:
    print("DENIED")

### FIXED CODE ###

x, y, z = input().split()
if x == y != z or x == z != y or x != y == z:
    print('Yes')
else:
    print('No')
l,r=map(int,input().split())
c=r-l
if c>=2018:
    print(0)
else:
    for i in range(l,r-1):
        for k in range(l+1,r):
            d=2018
            if (i*k)%2019<d:
                d=(i*k)&2019
    print(d)

### FIXED CODE ###

##C
l,r=map(int,input().split())
c=(r-l)
d=2018
if c>=2018:
    print(0)
else:
    for i in range(l,r):
        for k in range(l+1,r+1):
            
            if (i*k)%2019<d:
                d=(i*k)%2019
    print(d)
candy = sorted(list(map(int,input().split(' '))))
if candy[2]==(candy[0]+candy[1]):
    print('Yes')
else:
    print(No'')

### FIXED CODE ###

candy = sorted(list(map(int,input().split(' '))))
if candy[2]==(candy[0]+candy[1]):
    print('Yes')
else:
    print('No')
s,t=map(str,input.split())
print(t+s)

### FIXED CODE ###

s,t=map(str,input().split())
print(t+s)
n,k = map(int,input().split())
ans = 2*k+1
if ans > n:
  print(‘NO’)
else:
  print(‘YES’)

### FIXED CODE ###

n,k = map(int, input().split())
ans = 2*k-1
if n < ans:
  print('NO')
else:
  print('YES')
input = X
if X >= 30:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

X = int(input())
if(X >= 30):
  print('Yes')
else:
  print('No')
from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
for i in range(10**3+1):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
        else:
            t += 1
    if t == N:
        break
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
if ans == 1001:
    print(-1)
    exit()
print(ans-1)

### FIXED CODE ###

S = list(input())
T = list(input())
ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1
print(ans)
a=input()
a=map(int,raw_input().split())
print(str(min(a))+" "+max(a)+" "+sum(a))

### FIXED CODE ###

a=input()
a=map(int,raw_input().split())
print(str(min(a))+" "+str(max(a))+" "+str(sum(a)))
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    if l[i]==a:
        continue
    a = l[i]
    b = 0
    for j in range(i+1,n-1):
        if l[j]==b:
            continue
        b = l[j]
        c = 0 
        for k in range(j+1,n):
            if l[k]==c:
                continue
            c = l[k]
            if c-b < a:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        k = bisect_left(l,a+b)
        ans += k-j-1
print(ans)
a,b = map(int,input().split())

b = b*100
ans = int((a*b)/100)

### FIXED CODE ###

a,b = map(str,input().split())
b = list(b)
del b[-3]
b = ''.join(b)
b = int(b)
#print(b)
#b = int(b*10000)
ans = int(a)*b//100
print(int(ans))
a=input()
A=len(a)
b=x
for i in A-1:
  b=b+'x'
print(b)

### FIXED CODE ###

a=input()
A=len(a)
b="x"
for i in range(A-1):
  b=b+"x"
print(b)
n,k = map(int , input().split())
p = list(map(int , input()).split())
 
p1 = sorted(p)
 
temp = 0
for i in p1[:k] :
  temp += i
print(temp)

### FIXED CODE ###

n,k = map(int , input().split( ))
p = list(map(int , input().split( )))
 
p.sort()
 
temp = 0
for i in p[:k] :
  temp += i
print(temp)
N, M, C = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(N)]

result = len(
    row
    for row in A
    if C + sum([x * y for x, y in zip(row, B)]) > 0
)

print(result)

### FIXED CODE ###

N, M, C = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(N)]

result = 0

for row in A:
    t = C + sum([x * y for x, y in zip(row, B)])
    if t > 0:
        result += 1

print(result)
a  = money % 1000
if a > 0:
    change = 1000 - a
else:
    change = 0
print(change)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 20:25:04 2020

@author: KevinLU
"""
money = int(input())

a  = money % 1000
if a > 0:
    change = 1000 - a
else:
    change = 0
print(change)
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			print("select",i)
			return(b)
		else:
			return(a)

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])