Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
tasks = [list(map(int, input().split())) for i in range(N)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")

Fixed submission:
n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i],b[i]=map(int,input().split())

for i in range(n):
  suma=sum(a)
  maxb=max(b)
  if suma<=maxb:
    index=b.index(maxb)
    del a[index]
    del b[index]
  else:
    print('No')
    exit()
print('Yes')


Fixed submission:
n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i],b[i]=map(int,input().split())

for i in range(n):
  suma=sum(a)
  maxb=max(b)
  if suma<=mxb:
    index=b.index(maxb)
    del a[index]
    del b[index]
  else:
    print('No')
    exit()
print('Yes')


Fixed submission:
n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[n]
b=[n]
for i in range(n):
  a[i],b[i]=map(int,input().split())

for i in range(n):
  suma=sum(a)
  maxb=max(b)
  if suma<=mxb:
    index=b.index(maxb)
    del a[index]
    del b[index]
  else:
    print('No')
    exit()
print('Yes')


Fixed submission:
n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
b=[]
for i in range(n):
  tmpa,tmpb=map(int,input().split())
  a.append(tmpa)
  b.append(tmpb)

for i in range(n):
  if sum(a)<=max(b):
    index=b.index(max(b))
    del a[index]
    del b[index]
  else:
    print('No')
    exit()
print('Yes')

Fixed submission:
n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
age = int(print())
if age==7 || age==5 || age==3:
  print('YES')
else:
  print('NO')



Fixed submission:
age = int(input())
if age == 7 or age == 5 or age == 3:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
n=int(input())
t,a=map(int,input().split())
h=list(map(lambda x: abs(a-(t-int(x)*0.006)) ,input().split())
print(h.index(min(h))+1)

Fixed submission:
n=int(input())
t,a=map(int,input().split())
ans=0
min=1000000000
h=list(map(int, input().split()))
for i in range(n):
  b=t-h[i]*0.006
  if min>abs(a-b):
    ans=i+1
    min=abs(a-b)
print(ans)
Buggy python submission (verdict: Runtime Error):
n, a, b = [int(input()) for i in range(3)]
if n==1:
  print('Hello World')
else:
  print(a+b)
  
  


Fixed submission:
n = int(input())
if n == 1:
    print('Hello World')
else:
    a, b = [int(input()) for i in range(2)]
    print(a+b)
Buggy python submission (verdict: Runtime Error):
N,T=map(int,input())
ans=100000000
for i in range(n):
  c,t=map(int,input().split())
  if t>T: continue
  ans=min(c,ans)
print(ans if ans<100000000 else 'TLE')

Fixed submission:
N,T=map(int,input().split())
ans=100000000
for i in range(N):
  c,t=map(int,input().split())
  if t>T: continue
  ans=min(c,ans)
print(ans if ans<100000000 else 'TLE')
Buggy python submission (verdict: Runtime Error):
s = input()
for i in range(len(s)):
  if s[i]=='1':
    s[i]='9'
  else:
    s[i]='1'

print(s)

Fixed submission:
s = input()
s = s.replace('1','2')
s = s.replace('9','1')
s = s.replace('2','9')
print(s)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
print'No' if a%2==0 or b%2==0 else 'Yes'

Fixed submission:
a, b = map(int, input().split())
print('No' if a%2==0 or b%2==0 else 'Yes')

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
print(a%2==0 or b%2==0 ? 'No' : 'Yes')


Fixed submission:
a, b = map(int, input().split())
print('No' if a%2==0 or b%2==0 else 'Yes')
Buggy python submission (verdict: Runtime Error):
n=int(input())
w=[int(x) for x in input().split()]
ans='Yes'
for i in range(1,n):
  if w[i-1][-1]!=w[i][0]:
    ans='No'
    break
  for j in range(i):
    if w[i]==w[j]:
      ans='No'
      break
print(ans)


Fixed submission:
n=int(input())
w=[input() for _ in range(n)]
ans='Yes'
for i in range(1,n):
  if w[i-1][-1]!=w[i][0]:
    ans='No'
    break
  for j in range(i):
    if w[i]==w[j]:
      ans='No'
      break
print(ans)
Buggy python submission (verdict: Runtime Error):
k = input()
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)


Fixed submission:
k = int(input())
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)

Buggy python submission (verdict: Runtime Error):
k = input()
if k % 2 == 1:
    print((k//2) * (k//2+1))
else:
    print((k//2) * (k//2))


Fixed submission:
k = int(input())
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)

Buggy python submission (verdict: Runtime Error):
k = map(int, input().split())
if k%2==1:
  print((k//2) * (k//2+1))
else:
  print((k//2) * (k//2))


Fixed submission:
k = int(input())
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)

Buggy python submission (verdict: Runtime Error):
k = map(int, input().split())
if k%2==1:
  print((k//2) * (l//2+1))
else:
  print((k//2) *(k//2))

Fixed submission:
k = int(input())
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
a=[]
for i in range(h):
  tmp=input()
  if len(tmp)!=tmp.count('.'):
    a.append(tmp)
  else:
    h-=1
    
a=list(zip(*a))
for i in range(w):
  if len(a[i])==a[i].count('.'):
    del a[i]
    w-=1
    i-=1
    
a=list(zip(*a))
for i in range(h):
  print(a[i])
      


Fixed submission:
h,w=map(int,input().split())
a=[]
for i in range(h):
  tmp=input()
  if len(tmp)!=tmp.count('.'):
    a.append(tmp)
  else:
    h-=1

b=[]
for i in range(w):
  cnt=0
  for j in range(h):
    if a[j][i]=='.':
      cnt+=1
  if cnt==h:
    b.append(0)
  else:
    b.append(1)

for i in range(h):
  for j in range(w):
    if b[j]:
      print(a[i][j], end='')
  print()
Buggy python submission (verdict: Runtime Error):
s,t=input().split()
for i in range(1,len(s)+1):
  if t==s[-i:]+s[:-i]:
    print('Yes')
    exit()
print('No')

Fixed submission:
s=input()
t=input()
for i in range(1,len(s)+1):
  if t==s[-i:]+s[:-i]:
    print('Yes')
    exit()
print('No')
Buggy python submission (verdict: Runtime Error):
n=input()
a=list(map(int, input().split()))
ans=0 
for i in range(n):
  for j in range(i+1, n):
    ans=max(ans, abs(a[i]-a[j]))
print(ans)

Fixed submission:
n=int(input())
a=[int(x) for x in input().split()]
ans=0 
for i in range(n):
  for j in range(i+1, n):
    ans=max(ans, abs(a[i]-a[j]))
print(ans)

Buggy python submission (verdict: Runtime Error):
n=input()
a=[int(x) for x in input().split()]
ans=0
for i in range(n):
  for j in range(i+1, n):
    ans=max(ans, abs(a[i]-a[j]))
print(ans)

Fixed submission:
n=int(input())
a=[int(x) for x in input().split()]
ans=0 
for i in range(n):
  for j in range(i+1, n):
    ans=max(ans, abs(a[i]-a[j]))
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
n=0
for x in s: n += int(x)
print('Yes' if s%n==0 else 'No')

Fixed submission:
s=input()
n=0
for x in s: n += int(x)
print('Yes' if int(s)%n==0 else 'No')
Buggy python submission (verdict: Runtime Error):
a=list(map(int,input().split()))
for _ in range(int(input()):
  a.sort()
  a[2]*=2
print(sum(a))

Fixed submission:
a=list(map(int,input().split()))
k=int(input())
for _ in range(k):
  a.sort()
  a[2]*=2
print(sum(a))
Buggy python submission (verdict: Runtime Error):
a, b, x = map(int, input())
if a<=x:
  print('YES')
elif a+b>=x:
  print('YES')
else:
  print('NO')

Fixed submission:
a, b, x = map(int, input().split())
if a==x:
  print('YES')
elif a<x and a+b>=x:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
n,m,x=map(int,input().split())
a=[0]*(n+1)
for i in input().split(): a[int(i)]=1
print(min(sum(a[x:n]),sum(a[0:x]))

Fixed submission:
n,m,x=map(int,input().split())
a=[0]*(n+1)
for i in input().split(): a[int(i)]=1
print(min(sum(a[x:n]),sum(a[0:x])))
Buggy python submission (verdict: Runtime Error):
s = input()
print((s in 'a') and (s in 'b') and (s in 'c') ? 'Yes' : 'No')


Fixed submission:
s = input()
print('Yes' if ('a' in s) and ('b' in s) and ('c' in s) else 'No')
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int, input().split())
print(min(a,b)+min(c,d))

Fixed submission:
a = [int(input()) for i in range(4)]
print(min(a[0], a[1])+min(a[2], a[3]))
Buggy python submission (verdict: Runtime Error):
import math

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

d={'M':0,'A':0,'R':0,'C':0,'H':0}
n=int(input())
for i in range(n):
  word=input()
  if word[0] in d: d[word[0]]+=1

m = sum(d.values())
max = combinations_count(m,3)

if m<3:
  print(0)
  exit()

sub = 0
for i in d.values():
  if i>=3: sub += combinations_count(i, 3)
  if i>=2: sub += combinations_count(i, 2) * (m-2)

print(max - sub)


Fixed submission:
comp='MARCH'
cnt=[0,0,0,0,0]

n=int(input())
for i in range(n):
  word=input()
  for j in range(len(comp)):
    if word[0]==comp[j]: cnt[j]+=1

ans = 0
for i in range(len(cnt)):
  for j in range(i+1, len(cnt)):
      for k in range(j+1, len(cnt)):
        ans += cnt[i]*cnt[j]*cnt[k]
        
print(ans)

Buggy python submission (verdict: Runtime Error):
import math

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

d={'M':0,'A':0,'R':0,'C':0,'H':0}
n=int(input())
for i in range(n):
  word=input()
  if word[0] in d:d[word[0]]+=1

m = sum(d.values())
max = combinations_count(m,3) if m!=0 else 0
sub = 0
for i in d.values():
  if i>2: sub += combinations_count(i, 3)
  elif i>1: sub += combinations_count(i, 2) * (m-2)

print(max - sub)

Fixed submission:
comp='MARCH'
cnt=[0,0,0,0,0]

n=int(input())
for i in range(n):
  word=input()
  for j in range(len(comp)):
    if word[0]==comp[j]: cnt[j]+=1

ans = 0
for i in range(len(cnt)):
  for j in range(i+1, len(cnt)):
      for k in range(j+1, len(cnt)):
        ans += cnt[i]*cnt[j]*cnt[k]
        
print(ans)
Buggy python submission (verdict: Runtime Error):
ans = int(input())-int(input())
print(ans if ans>0 else 0)


Fixed submission:
x,t=map(int,input().split())
ans = x - t
print(ans if ans>0 else 0)
Buggy python submission (verdict: Runtime Error):
print((int(input())-1)*(int(input())-1))

Fixed submission:
m,n=map(int,input().split())
print((m-1)*(n-1))
Buggy python submission (verdict: Runtime Error):
x,a,b=map(int,input().split())
print('delicious' if b-a<=0 else 'safe' if b-a<x+1 else 'dangerous
')

Fixed submission:
x,a,b=map(int,input().split())
print('delicious' if b-a<=0 else 'safe' if b-a<x+1 else 'dangerous')
Buggy python submission (verdict: Runtime Error):
r,g,b=input().split()
print('YES' if eval('r+g+b%4==0') else 'NO')

Fixed submission:
r,g,b=input().split()
print('YES' if int(r+g+b)%4==0 else 'NO')
Buggy python submission (verdict: Runtime Error):
a,b,c=input().split()
print(upper(a[0]+b[0]+c[0])

Fixed submission:
a,b,c=input().split()
print((a[0]+b[0]+c[0]).upper())
Buggy python submission (verdict: Runtime Error):
a,b=input().split()
sum=a+b
print(sum if sum<24 else sum-24)

Fixed submission:
a,b=map(int,input().split())
sum=a+b
print(sum if sum<24 else sum-24)
Buggy python submission (verdict: Runtime Error):
S=input()
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
  print("Bad")
 else:
  print("Good")

Fixed submission:
s = input()
a = 13
c = 0
for i in s:
  if int(i) == a:
    c = 1
    break 
  a = int(i)
 
if c==1:
  print("Bad")
else:
  print("Good")
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if sum(A,B,C) == 17:
  print("YEAS")
else:
  print("NO")
  

Fixed submission:
A, B, C = map(int, input().split())
if A*B*C == 5*5*7:
  print("YES")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
nums = list(input().split())
if sum(nums) == 17:
  print("YES")
else:
  print("NO")
  

Fixed submission:
A, B, C = map(int, input().split())
if A*B*C == 5*5*7:
  print("YES")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
numlist = list(input())
if sum(numlist) == 17:
  print("YES")
else:
  print("NO")
  

Fixed submission:
A, B, C = map(int, input().split())
if A*B*C == 5*5*7:
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
import bisect as bi


def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    for _ in range(M):
        Max = A.pop()
        bi.insort(A, Max//2)
    print(sum(A))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
import heapq as q
import math

def solve(N: int, M: int, A: "List[int]"):
    q.heapify(A)
    for _ in range(M):
        Max = q.heappop(A)
        q.heappush(A, math.ceil(Max/2))
    print(-sum(A))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [-int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

MAX = max(a)

for i in range(n):
    if a[i] == MAX:
        print(max(a[:i] + a[i+1:]))
    else:
        print(MAX)


Fixed submission:
n = int(input())
a = {}
for i in range(n):
    a[i] = int(input())

max_i, MAX = max(a.items(), key=lambda x: x[1])
del a[max_i]

SECOND = max(a.values())


for i in range(n):
    if i == max_i:
        print(SECOND)
    else:
        print(MAX)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

for i in range(n):
    print(max(a[:i] + a[i+1:]))


Fixed submission:
n = int(input())
a = {}
for i in range(n):
    a[i] = int(input())

max_i, MAX = max(a.items(), key=lambda x: x[1])
del a[max_i]

SECOND = max(a.values())


for i in range(n):
    if i == max_i:
        print(SECOND)
    else:
        print(MAX)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


n = int(input())
lines = []
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.insert(0, a)
        continue
    
    lines[index - 1] = a

print(len(lines))


Fixed submission:
import bisect
from collections import deque


n = int(input())
lines = deque()
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.appendleft(a)
        continue
    
    lines[index - 1] = a

print(len(lines))
Buggy python submission (verdict: Time Limit Exceeded):
def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n

# calc
for i in range(1, n):
    d_i = [(dp[i+k-(j+1)] + abs(h[i] - h[i-(j+1)]) if j < i else inf) for j in range(k)]
    # print(i, d_i, dp)
    dp[i+k] = min(d_i)

print(dp[-1])


"""
"""


Fixed submission:
import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""

Buggy python submission (verdict: Time Limit Exceeded):
def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n
d = [[inf] * j + [abs(h[i+j] - h[i]) for i in range(n-j)] for j in range(1, k+1)]

# calc
for i in range(1, n):
    d_i = [dp[i-j+k] + d[j-1][i] for j in range(1, k+1)]
    dp[i+k] = min(d_i)

print(dp[-1])


"""
"""


Fixed submission:
import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""

Buggy python submission (verdict: Time Limit Exceeded):
def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n
d = [[inf] * j + [abs(h[i+j] - h[i]) for i in range(n-j)] for j in range(1, k+1)]
# print(d)

# calc
for i in range(1, n):
    d_i = []
    for j in range(1, k+1):
        d_i_j = dp[i-j+k] + d[j-1][i]
        # print(i, j, d_i_j, i-j+k, dp[i-j+k], j-1, d[j-1][i])

        d_i.append(d_i_j)

    # print(i, d_i)

    dp[i+k] = min(d_i)
# print(dp)

print(dp[-1])
"""
"""


Fixed submission:
import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""
Buggy python submission (verdict: Time Limit Exceeded):
import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def n(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

N = n()
abc = bulk_li()  # [[a_i, b_i, c_i]...]

# print(abc)

T = [
    [1, 2],
    [0, 2],
    [0, 1]
]

def solve(abc):
    dp = np.zeros((N, 3), dtype='int32')  # [[Ai, Bi, Ci]...]

    for j in range(3):
        dp[0][j] = abc[0][j]
    if N == 1:
        return dp

    for i in range(N-1):
        dp[i+1][0] = abc[i+1][0] + np.max(dp[i][[1,2]])
        dp[i+1][1] = abc[i+1][1] + np.max(dp[i][[0,2]])
        dp[i+1][2] = abc[i+1][2] + np.max(dp[i][[0,1]])

    # print(dp)
    return dp

print(max(solve(abc)[N-1]))


"""
ちゃんと解いたVer
"""


Fixed submission:
n = int(input())
a, b, c = list(map(int, input().split()))

if n > 1:
    for _ in range(n-1):
        a_, b_, c_ = list(map(int, input().split()))
        a_ += max(b, c)
        b_ += max(a, c)
        c_ += max(a, b)
        a, b, c = a_, b_, c_

print(max(a, b, c))
"""
ちゃんと解いたVer
"""

Buggy python submission (verdict: Runtime Error):
import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def n(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

N = n()
abc = bulk_li()  # [[a_i, b_i, c_i]...]

dp = np.zeros((N, 3), dtype='int32')  # [[Ai, Bi, Ci]...]
# fl = np.zeros((N, 3), dtype='int32')  # [[fl_ai, fl_bi, fl_ci]...]
choice = np.ones((3,3)) - np.diag([1]*3)

S = [
    [0, 1],
    [0, 2],
    [1, 0],
    [1, 2],
    [2, 0],
    [2, 1],
]

T = [
    [[1, 1], [2, 2]],
    [[0, 0], [2, 2]],
    [[0, 0], [1, 1]]
]

for j in range(3):
    dp[0][j] = abc[0][j]
    dp[1][j] = max(abc[0]) + abc[1][j]

for i in range(N-2):
    for j in range(3):
        pattern = S + T[j]
        next = [dp[i][j] + abc[i+1][j_] for j, j_ in pattern]
        # print(i, j, next)
        dp[i+2][j] = max(next) + abc[i+2][j]

# print(abc)
# print(dp)
print(max(dp[N-1]))


"""

"""


Fixed submission:
n = int(input())
a, b, c = list(map(int, input().split()))

if n > 1:
    for _ in range(n-1):
        a_, b_, c_ = list(map(int, input().split()))
        a_ += max(b, c)
        b_ += max(a, c)
        c_ += max(a, b)
        a, b, c = a_, b_, c_

print(max(a, b, c))
"""
ちゃんと解いたVer
"""
Buggy python submission (verdict: Time Limit Exceeded):
import os, sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))


"""
TLE
https://atcoder.jp/contests/dp/submissions/6675353

recursionでやると遅い。
"""


Fixed submission:
import numpy as np
N, W = map(int, input().split())
ndp = np.zeros(W+1, dtype= np.int64)
for _ in range(N):
    w, v = map(int,input().split())

    # 離散より連続で扱った方が簡単になる。
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])


"""
https://atcoder.jp/contests/dp/submissions/6657472
より失敬。

めっちゃスマートな解法。
"""

Buggy python submission (verdict: Time Limit Exceeded):
import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))


Fixed submission:
import numpy as np
N, W = map(int, input().split())
ndp = np.zeros(W+1, dtype= np.int64)
for _ in range(N):
    w, v = map(int,input().split())

    # 離散より連続で扱った方が簡単になる。
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])


"""
https://atcoder.jp/contests/dp/submissions/6657472
より失敬。

めっちゃスマートな解法。
"""