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

import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None

if D.count(0)==1 and D[0]==0:

    mul=1
    n=1

    for i in range(1,max(D)+1):
        m=D.count(i)
        n=n%998244353
        mul*=n**m%998244353
        n=m
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

### FIXED CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None


if D.count(0)==1 and D[0]==0:

    L=[0]*(max(D)+1)

    for i in range(len(D)):
        L[D[i]]+=1

    mul=1

    for i in range(len(L)-1):
        mul*=L[i]**L[i+1]%998244353
    
    ans=mul%998244353

else:
    ans=0

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

N = int(input())

def get_cands(x, y, h):
    if h > 0:
        for xc in range(100 + 1):
            for yc in range(100 + 1):
                hc = h + abs(xc - x) + abs(yc - y)
                if hc <= 10**9:
                    yield (xc, yc, hc)
    else:
        for xc in range(100 + 1):
            for yc in range(100 + 1):
                hc = h + abs(xc - x) + abs(yc - y)
                for hc2 in range(1, hc + 1):
                    if hc <= 10**9:
                        yield (xc, yc, hc2)

x1, y1, h1 = map(int, input().split())
cand = set(get_cands(x1, y1, h1))

for _ in range(N - 1):
    new_cand = set()
    x, y, h = map(int, input().split())
    for c in get_cands(x, y, h):
        if c in cand:
            new_cand.add(c)
    cand = new_cand
    if len(cand) == 1:
        break
if len(cand) == 1:
    print(*next(iter(cand)))
else:
    while True:
        pass

### FIXED CODE ###

N = int(input())
XYH = [[int(x) for x in input().split()] for _ in range(N)]

def get_cands(x, y, h):
    for xc in range(100 + 1):
        for yc in range(100 + 1):
            hc = h + abs(xc - x) + abs(yc - y)
            yield (xc, yc, hc)

def is_valid(top, view):
    xt, yt, ht = top
    xv, yv, hv = view
    return hv == max(0, ht - abs(xt - xv) - abs(yt - yv))

cand = set(get_cands(*next(filter(lambda x: x[2] > 0, XYH))))
ans = filter(lambda x: all(is_valid(x, v) for v in XYH), cand)

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

K,S=[int(i) for i in input().split()]
count=0
for i in range(0,K+1):
        for j in range(0,K+1):
            for k in range(0,K+1):
                 if i+j+k==S:
                    count+=1
print(count)

### FIXED CODE ###

K,S=[int(i) for i in input().split()]
count=0
for i in range(0,K+1):
        for j in range(0,K+1):
            k=S-i-j
            if 0<=k<=K:
                count+=1
print(count)
### BUGGY CODE ###

#-*-coding:utf-8-*-
from collections import Counter

def main():
    n, k = map(int, input().split())
    a_list = list(input().split())
    a_set = set(a_list)

    c = Counter(a_list)

    cnt = 0
    for i in range(len(a_set) - k):
        cnt += c.most_common()[::-1][i][1]

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
#from collections import Counter

def main():
    n, k = map(int, input().split())
    a_list = list(input().split())
    a_set = set(a_list)

    #c = Counter(a_list)
    dic = {}
    for i in a_list:
        dic.setdefault(i, 0)
        dic[i] += 1

    freq = sorted(dic.values())

    cnt = 0
    for i in range(len(a_set) - k):
        cnt += freq[i]
        #cnt += c.most_common()[::-1][i][1]

    print(cnt)

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

import math
MOD = pow(10, 9)+7
N, M = map(int, raw_input().split())

if abs(N - M) > 1:
	print 0
else:
	if N == M:
		res = ( math.factorial(N) * math.factorial(N) * 2 )%MOD
	else:
		res = ( math.factorial(N) * math.factorial(M) )%MOD
	print res

### FIXED CODE ###

MOD = pow(10, 9)+7
N, M = map(int, raw_input().split())

def myfact(num):
	res = 1
	for i in range(num+1)[1:]:
		res *= i
		if res > MOD:
			res %= MOD
	return res
if abs(N - M) > 1:
	print 0
else:
	if N == M:

		res = ( myfact(N) * myfact(N) * 2 )%MOD
	else:
		res = ( myfact(N) * myfact(M) )%MOD
	print res
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
x=[]
for i in range(1,n+1):
    for t in range(n):
        if a[t]==i:
            num=t+1
            x.append(num)
for q in x:
    print(q,end=" ")

### FIXED CODE ###

n=int(input())
a = list(map(int, input().split()))
x=[[] for _ in range(n)]
for i in range(n):
    x[a[i]-1] = i + 1
print(' '.join(map(str,x)))
### BUGGY CODE ###

### LCS 
# dp[i][j]: s[i],t[j]までの最長部分文字列の長さ
# s[i]==t[j]だったらs[i-1][j-1]+1,
# それ以外の場合はmax(s[i-1][j],s[i][j-1])

s= input()
t= input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si==tj:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

ans =""
n = dp[-1][-1]
i = len(s)
j =len(t)
while n >0:
    if dp[i][j]==dp[i-1][j]:
        i-= 1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans = s[i-1]+ans
        n-=1
        i-=1
        j-=1

print(ans)



### FIXED CODE ###

### LCS 
# dp[i][j]: s[i],t[j]までの最長部分文字列の長さ
# s[i]==t[j]だったらs[i-1][j-1]+1,
# それ以外の場合はmax(s[i-1][j],s[i][j-1])

s= input()
t= input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si==tj:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

ans =""
n = dp[-1][-1]
i = len(s)
j =len(t)
while n >0:
    if dp[i][j]==dp[i-1][j]:
        i-= 1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans = s[i-1]+ans
        n-=1
        i-=1
        j-=1

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

n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)]for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = bin(a[i])
    k = list(map(int, k[:1:-1]))
    k = k + [0 for i in range(leng - len(k))]
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = list(input())
n = len(s)
s.reverse()
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        for j in range(13):
            k = j - (s1*(10**i))%13
            if k < 0:
                k = k + 13
            else:
                k = k % 13
            dp[i][j] = dp[i-1][k]
    else:
        for j in range(13):
            for x in range(10):
                k = j - (x*((10**i)%13))%13
                if k < 0:
                    k = k + 13
                else:
                    k = k % 13
                dp[i][j] = (dp[i-1][k] + dp[i][j])%(10**9 + 7)
print(dp[n-1][5])

### FIXED CODE ###

s = list(input())
n = len(s)
s.reverse()
m = 10**9 + 7
p = 10
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        k = (s1*p)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for x in range(10):
            k = (x*p)%13
            for j in range(13):
                dp[i][(j+k)%13] += dp[i-1][j]
                dp[i][(j+k)%13] %= m
    p = (p * 10) % 13
print(dp[n-1][5])
### BUGGY CODE ###

n,m=map(int,input().split())
path=[[] for i in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
S,T=map(int,input().split())

que=[S]
flag=[0]*(n+1)
flag[S]=1
data=[[] for i in range(n+1)]

while que:
    h=que.pop()
    lst=[h]
    for i in range(3):
        u=[]
        for j in lst:
            for k in path[j]:
                u.append(k)
        lst=u
    lst=list(set(lst))
    for i in lst:
        if i==h:
            continue
        data[h].append(i)
        if flag[i]==0:
            flag[i]=1
            que.append(i)

que=[S]
flag=[0]*(n+1)
flag[S]=1
count=0
while que:
    count+=1
    H=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                H.append(v)
                flag[v]=1
            if v==T:
                print(count)
                break
        else:
            continue
        break
    else:
        que=H
        continue
    break
else:
    print(-1)

### FIXED CODE ###

n,m=map(int,input().split())
data=[[] for i in range(3*n+1)]
for i in range(m):
    u,v=map(int,input().split())
    data[u].append(v+n)
    data[u+n].append(v+2*n)
    data[u+2*n].append(v)
s,t=map(int,input().split())
inf=float("inf") 
flag=[inf]*(3*n+1)
flag[s]=0
que=[s]
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==inf:
                flag[v]=flag[u]+1
                h.append(v)
    que=h
if flag[t]==inf:
    print(-1)
else:
    print(flag[t]//3)
### BUGGY CODE ###

n = int(input())
T = list(map(int, input().split()))
t = [0]
for i in range(n):
	t.append(t[-1] + T[i])
v = list(map(int, input().split()))

ans = 0
prev_spped = 0

for x in range(1, 2 * t[-1] + 1):
	time = x / 2
	speeds = [time, t[-1] - time]
	for i in range(n):
		if time <= t[i]:
			speeds.append(v[i] + t[i] - time)
		elif t[i] < time <= t[i + 1]:
			speeds.append(v[i])
		else:
			speeds.append(v[i] + time - t[i + 1])
	speed = min(speeds)
	ans += (speed + prev_spped) * 0.25
	prev_spped = speed

print(ans)

### FIXED CODE ###

n = int(input())
T = list(map(int, input().split()))
t = [0]
for i in range(n):
	t.append(t[-1] + T[i])
v = list(map(int, input().split()))

ans = 0
prev_spped = 0

for x in range(1, 2 * t[-1] + 1):
	time = x / 2
	speeds = [time, t[-1] - time]
	for i in range(n):
		if time <= t[i]:
			speeds.append(v[i] + t[i] - time)
		elif t[i] < time <= t[i + 1]:
			speeds.append(v[i])
		else:
			speeds.append(v[i] + time - t[i + 1])
	speed = min(speeds)
	ans += (speed + prev_spped) * 0.25
	prev_spped = speed

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

import sys

N = int(sys.stdin.readline())
TXY = [
    tuple(map(int, sys.stdin.readline().split())) for _ in range(N)
]

def check(st, sx, sy, et, ex, ey):
    points = [(sx, sy)]
    for _ in range(et - st):
        new_points = set()
        for px, py in points:
            new_points.add((px + 1, py))
            new_points.add((px - 1, py))
            new_points.add((px, py + 1))
            new_points.add((px, py - 1))
        points = list(new_points)
    if (ex, ey) in points:
        return True
    return False


def main():
    TXY.insert(0, (0, 0, 0))
    for i in range(len(TXY) - 1):
        args = TXY[i] + TXY[i + 1]
        if not check(*args):
            print('No')
            return
    print('Yes')

main()

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
TXY = [
    tuple(map(int, sys.stdin.readline().split())) for _ in range(N)
]

def check(st, sx, sy, et, ex, ey):
    timespan = et - st
    diff = abs(sx - ex) + abs(sy - ey)
    if diff > timespan:
        return False
    if (timespan - diff) % 2 == 0:
        return True
    return False


def main():
    TXY.insert(0, (0, 0, 0))
    for i in range(len(TXY) - 1):
        args = TXY[i] + TXY[i + 1]
        if not check(*args):
            print('No')
            return
    print('Yes')

main()
### BUGGY CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

A,B,C,K = MI()
ans = 0
while K>0:
    if A>0:
        ans+= 1
        A -= 1
    elif B>0:
        B -= 1
    else:
        ans -= 1
        C -= 1
    K -= 1
print(ans)


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

A,B,C,K = MI()
ans = 0
if K<=A:
    print(K)
elif K<=A+B:
    print(A)
else:
    print(2*A+B-K)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * (N+10)

def dfs(now, par, len):
    ng = -1
    ok = len+5
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[now] <= dp[mid]:
            ok = mid
        else:
            ng = mid
    memo = dp[ok]
    dp[ok] = A[now]

    ng1 = 0
    ok1 = len+5
    while ok1 - ng1 > 1 :
        mid = (ok1 + ng1) // 2
        if dp[mid] == INF:
            ok1 = mid
        else:
            ng1 = mid
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

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


### FIXED CODE ###

import sys
import bisect
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * N

def dfs(now, par, len):
    ok = bisect.bisect_left(dp, A[now])
    memo = dp[ok]
    dp[ok] = A[now]

    ok1 = bisect.bisect_left(dp, INF)
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

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

n = int(input())
v = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= v[i]
if (ans > 10**18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
if 0 in v:
    print(0)
    exit()
ans = 1
for i in range(n):
    ans *= v[i]
    if (ans > 10**18):
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=ans*li[i]
if ans<=10**18:
    print(ans)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
d = [0]*(n+1)
count = 0
for el in a:
    temp = d[el]
    if temp == 0:
        temp = a.count(el)
        d[el] = temp
        count += temp*(temp-1)
count //= 2
for el in a:
    print(count - d[el] + 1)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
d = [0]*(n+1)
count = 0
for el, cnt in counter.most_common():
    d[el] = cnt
    count += cnt*(cnt-1)
count //= 2
for el in a:
    print(count - d[el] + 1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def Knapsack1(w0,W,w,v): # n個の品物(重さw[i],価値v[i]) 総重量W以内での価値の最大化 計算量O(W*N)
    n=len(w)
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp=[[0 for _ in range((w0+3)*n+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(W+1):
            dp[i][j]=max( dp[i][j],dp[i-1][j] )
            if j >= w[i-1]+w0:
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]-w0]+v[i-1])
    print(max(dp[n]))


def main():
    n,W = inpm()
    w = []
    v = []
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        w.append(wv[0]-w0)
        v.append(wv[1])
    Knapsack1(w0,W,w,v)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,W = inpm()
    v = [[] for _ in range(4)]
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        v[ wv[0]-w0 ].append(wv[1])
    for i in range(4):
        v[i] = sorted(v[i])
        v[i].reverse()
        vv = [0 for _ in range(len(v[i])+1)]
        for j in range(len(v[i])):
            vv[j+1] = vv[j] + v[i][j]
        v[i] = vv
    ans = 0
    for n1 in range(len(v[0])):
        for n2 in range(len(v[1])):
            for n3 in range(len(v[2])):
                for n4 in range(len(v[3])):
                    if W < w0*(n1+n2+n3+n4) + n2 + n3*2 + n4*3:
                        continue
                    ans = max(ans,v[0][n1]+v[1][n2]+v[2][n3]+v[3][n4])
    print(ans)

if __name__ == "__main__":
    main()