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

class Segtree():  # Segtree

    def segfunc(self, x, y):  # 区間にしたい操作
        return max(x, y)  # ex) max,min,gcd,lcm,sum,product

    def __init__(self, LIST, ide_ele):  # LIST: 配列の初期値, ide_ele: 単位元
        n = len(LIST)
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):  # 配列の値を葉にセット
            self.tree[self.num + i] = LIST[i]
        for i in range(self.num - 1, 0, -1):  # 構築していく
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):  # k番目の値をxに更新
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):  # [l, r)のsegfuncしたものを得る
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = Segtree([0] * (n + 1), 0)
for ai, hi in zip(a, h):
    dp.update(hi, dp.query(0, hi) + ai)
print(dp.query(0, n + 1))


### FIXED CODE ###

class Segtree():  # Segtree

    def segfunc(self, x, y):  # 区間にしたい操作
        return max(x, y)  # ex) max,min,gcd,lcm,sum,product

    def __init__(self, LIST, ide_ele):  # LIST: 配列の初期値, ide_ele: 単位元
        n = len(LIST)
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):  # 配列の値を葉にセット
            self.tree[self.num + i] = LIST[i]
        for i in range(self.num - 1, 0, -1):  # 構築していく
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):  # k番目の値をxに更新
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):  # [l, r)のsegfuncしたものを得る
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = Segtree([0] * (n + 1), 0)
for ai, hi in zip(a, h):
    dp.update(hi, dp.query(0, hi) + ai)
print(dp.query(0, n + 1))
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
PY_list = [[int(x)-1 for x in input().split()] for _ in range(M)]
lst = [[] for _ in range(N)] 
for P, Y in PY_list:
    lst[P].append(Y)
for i in range(N):
    lst[i] = sorted(lst[i])
for p, y in PY_list:
    print('{:06}{:06}'.format(p+1, lst[p].index(y)+1))


### FIXED CODE ###

from bisect import bisect_left
N, M = [int(x) for x in input().split()]
PY_list = [[int(x)-1 for x in input().split()] for _ in range(M)]
lst = [[] for _ in range(N)] 
for P, Y in PY_list:
    lst[P].append(Y)
for l in lst:
    l.sort()
for p, y in PY_list:
    print('{:06}{:06}'.format(p+1, bisect_left(lst[p], y)+1))
### BUGGY CODE ###

import sys
input=sys.stdin.readline


n,k=map(int,input().split())
cst=list(map(int,input().split()))
arr=[0]*(n+1)
arr[0]=0
arr[1]=abs(cst[1]-cst[0])
if n==2:
    print(arr[1])
else:
    for i in range(2, n):
        #arr[i] = min(abs(cst[i - 1] - cst[i]) + arr[i - 1], abs(cst[i - 2] - cst[i]) + arr[i - 2])
        #t=cst.index(min(cst[max(i-k,0):i]))
        #arr[i]=min(abs(cst[max(i-j,0)]-cst[i])+arr[i-j] for j in range(1,k+1))
        arr[i]=min(abs(cst[j]-cst[i])+arr[j] for j in  range(max(i-k,0),i))
    print(arr[n-1])

#print(arr)

### FIXED CODE ###

import sys

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

def main():
    n, k = map(int, input().split())
    cst = list(map(int, input().split()))
    arr = [0] * n
    arr[1] = abs(cst[1] - cst[0])
    for i in range(2, n):
        arr[i] = min(abs(cst[j] - cst[i]) + arr[j] for j in range(max(i - k, 0), i))
    print(arr[n - 1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=input()
li=list(map(int,input().split()))

value=True
for i in range(1,len(li)):
  for j in range(i):
    if li[i]==li[j]:
      value=False
      break
if value:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

n=input()
li=list(map(int,input().split()))
li.sort()

value=True
for i in range(1,len(li)):
  if li[i]==li[i-1]:
    value=False
    break
if value:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

import re

s = input()

cnt = s.count('ABC')
cntsum = cnt
#print('cnt =', cnt)
s = re.sub('ABC', 'BCA', s)
#print('s =', s)

while cnt != 0:
    cnt = s.count('ABC')
    cntsum = cntsum + cnt
#    print('cnt =', cnt, 'cntsum =', cntsum)
    s = re.sub('ABC', 'BCA', s)
#    print('s =', s)

print(cntsum)


### FIXED CODE ###

s = input()
t = s.replace('BC', 'D')

a = 0 # 連続するaの数
ans = 0 # 答え

for i in t:
    if i == 'A':
        a += 1
    elif i == 'D':
        ans += a
    else:
        a = 0

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    idx = -1
    ans = n

    for i in range(1, n+1):
        if i in a:
            idx = a.index(i)
            a = a[idx+1:]
            ans -= 1
        else:
            break

    if ans == n:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    seek = 1

    for i in range(n):
        if a[i] == seek:
            seek += 1

    if seek == 1:
        ans = -1
    else:
        ans = n + 1 - seek

    print(ans)

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

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

hyouten = [1]*n
hyouten[0] = a[0]
for i in range(1, n):
    hyouten[i] = hyouten[i-1]*a[i]
#print(hyouten)
for i in range(k+1, n+1):
    hyouten[i-1] //= hyouten[i-k-1]
    if hyouten[i-1] > hyouten[i-2]:
        print("Yes")
    else:
        print("No")
#print(hyouten)

### FIXED CODE ###

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

for i in range(k+1, n+1):
    if a[i-1] > a[i-k-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [list(map(int, x.split()[2:])) for x in f_i]

unvisited = [v for v in range(n)]

distance = [999900001] * n
distance[0] = 0

class VCost:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost
    def __lt__(self, other):
        return self.cost < other.cost

import heapq

vcost = [VCost(0, 0)]

def dijkstra():
    while vcost:
        uc = heapq.heappop(vcost)

        if uc.cost > distance[uc.v]:
            continue
        
        unvisited.remove(uc.v)
        
        for v, c in zip(adj[uc.v][::2], adj[uc.v][1::2]):
            if v in unvisited:
                t_cost = uc.cost + c
                if t_cost < distance[v]:
                    distance[v] = t_cost
                    heapq.heappush(vcost, VCost(v, t_cost))



dijkstra()

for v, d in enumerate(distance):
    print(v, d)

### FIXED CODE ###

import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[]] * n
for x in f_i:
    x = list(map(int, x.split()))
    adj[x[0]] = (c_v for c_v in zip(x[3::2], x[2::2]))

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc, u = heapq.heappop(PQ)

        if uc > distance[u]:
            continue

        isVisited[u] = True
        
        for vc, v in adj[u]:
            if isVisited[v] == True:
                continue
            
            t_cost = distance[u] + vc
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()
### BUGGY CODE ###

N,M,*a=map(int,open(0).read().split())
dp=[0]*(N+1)
dp[0]=1
if 1 not in a:
    dp[1]=1
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)    

### FIXED CODE ###

N,M=map(int,input().split())
dp=[1]*(N+1)
for i in range(M):
    dp[int(input())]=0
for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)
### BUGGY CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(n*a+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*a+1):
            if k+x[i-1]<=n*a:
                if j>=1:
                    dp[i][j][k+x[i-1]]+=dp[i-1][j-1][k]
            dp[i][j][k]+=dp[i-1][j][k]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(n*a+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*a+1):
            if k+x[i-1]<=n*a:
                if j>=1:
                    dp[i][j][k+x[i-1]]+=dp[i-1][j-1][k]
            dp[i][j][k]+=dp[i-1][j][k]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

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

import math
N=int(input())
for n in range(1,N+1):
    ans=0
    if n<=5:
        print(ans)
        continue
    X=math.floor(n**0.5)
    for x in range(1,X+1):
        for y in range(1,x+1):
            for z in range(1,y+1):
                if x**2 + y**2 + z**2 + x*y + y*z + x*z==n:
                    if (x==y and y!=z and z!=x) or (x!=y and y==z and z!=x) or (x!=y and y!=z and z==x): 
                        ans+=3
                    elif x==y and y==z and z==x:
                        ans+=1
                    else:
                        ans+=6
    print(ans)



### FIXED CODE ###

N = int(input())
ans = [0] * 100000
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
if k==1:
    print(0)
    sys.exit()
while abs(n-k)<n:
    n=abs(n-k)
    
    if n==0:
        print(n)
        sys.exit()
else:
    print(n)

### FIXED CODE ###

import sys
n,k=map(int,input().split())
if n%k==0:
    print(0)
    sys.exit()
if n%k<abs(k-n%k):
    print(n%k)
else:
    print(abs(k-n%k))
### BUGGY CODE ###

# -*- coding: utf_8 -*-

from itertools import repeat

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)

if __name__ == "__main__":
    n = int(input())
    a = [int (x) for x in input().split()]
    q = int(input())
    m = [int (x) for x in input().split()]
    for i in m:
        print("yes") if rec(a, 0, 0, i) > 0 else print("no")

### FIXED CODE ###

# -*- coding: utf_8 -*-

from itertools import repeat
from itertools import combinations

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)


def makeCache(s):
    cache = {}
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            cache[sum(c)] = 1

    return cache

def loop(s, m):
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            if sum(c) == m:
                return 1

    return 0

if __name__ == "__main__":
    n = int(input())
    a = [int (x) for x in input().split()]
    q = int(input())
    m = [int (x) for x in input().split()]
    s = makeCache(a)
    for i in m:
        #print("yes") if rec(a, 0, 0, i) > 0 else print("no")
        #print("yes") if loop(a, i) > 0 else print("no")
        print("yes") if i in s else print("no")
### BUGGY CODE ###

N,Q = map(int,input().split())
S=input()
for _ in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    s = S[l-1:r]
    for i in range(len(s)-1):
        if s[i]=="A" and s[i+1]=="C":
            cnt += 1
    print(cnt)

### FIXED CODE ###

N,Q = map(int,input().split())
S=input()
ans_l = [0]*N
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        ans_l[i+1] = ans_l[i] + 1
    else:
        ans_l[i+1] = ans_l[i]
for _ in range(Q):
    l, r = map(int, input().split())
    ans = ans_l[r-1] - ans_l[l-1]
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(i//2 for i in map(int, input().split()))
m = max(A)
A.remove(m)
base = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i not in range(j,M+1,2*j):
			semi = False
			break
	if semi:
		base = i
		break
if base == 0:
	print(0)
else:
	print(((M // base) + 1)//2)

### FIXED CODE ###

N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
B = []
for i in A:
	B = B + [0]
	while i % 2 == 0:
		i //= 2
		B[-1] += 1
if len(set(B)) == 1:
	m = max(A)
	A.remove(m)
	base = 0
	for i in range(m,M+1,2*m):
		semi = True
		for j in A:
			if i % j != 0 or (i // j) % 2 == 0:
				semi = False
				break
		if semi:
			base = i
			break
	if base == 0:
		print(0)
	else:
		print(((M // base) + 1)//2)
else:
	print(0)
### BUGGY CODE ###

from sets import Set

input()
n_list=map(int, raw_input().split())
input()
m_list=map(int, raw_input().split())

n = len(n_list)

pool = Set([])

def func(idx, m):

    if m==0:
        return True
    if idx >= n:
        return False
    res = func(idx + 1, m) | func(idx + 1, m - n_list[idx])
    
    if res:
        pool.add(m)
    return res

for v in m_list:
    if v in pool:
        print "yes"
    else:
        print "yes" if func(0, v) else "no"

### FIXED CODE ###

input()
nlist=map(int, raw_input().split())
input()
qlist=map(int, raw_input().split())

n = len(nlist)

dic = {}

def func(idx, m):
    
    try:
        return dic[m][idx]
    except:
        pass

    if m==0:
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    elif idx > n-1:
        tmp=dic.get(m,{})
        tmp.update({idx: False})
        dic.update({m:tmp})
        
    elif func(idx+1, m):
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    elif func(idx+1, m-nlist[idx]):
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    else:
        tmp=dic.get(m,{})
        tmp.update({idx: False})
        dic.update({m:tmp})
        
    return dic[m][idx]


for q in qlist:
    # print dic
    print "yes" if func(0, q) else "no"
### BUGGY CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)

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

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print("k:", k)
        for x in range(j,j+k):
            vplus = 0
            for vi in range(i-1,-1,-1):
                if grid[vi][x] == '#':
                    break
                else:
                    vplus += 1
            for vi in range(i+1,h):
                if grid[vi][x] == '#':
                    break
                else:
                    vplus += 1
            ans = max(ans, vplus+k)
        j = j+k
print(ans)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

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

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

import itertools

n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
rs = [r-1 for r in rs]

inf = float('inf')
dists = [[inf] * n for _ in range(n)]
for i in range(n):
    dists[i][i] = 0

for mm in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dists[a][b] = c
    dists[b][a] = c

## Warshall–Floyd
for k in range(n):
    for i in range(n):
        for j in range(n):
            dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

tours = []
for perm in itertools.permutations(rs):
    d = 0
    for i in range(r-1):
        d += dists[perm[i]][perm[i+1]]
    tours.append(d)
print(min(tours))
    


### FIXED CODE ###

#import time
#t = time.time()
inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

for mm in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  ds[a][b] = c
  ds[b][a] = c

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])

#print(f'wf finished {time.time() - t}')
#t = time.time()

#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))

#print(f'search finished {time.time() - t}')
#t = time.time()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

a = list(input())
a.pop(-1)

Q = int(input())
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        a.reverse()
    else:
        if q[1] == "1":
            a.insert(0, q[2])
        else:
            a.append(q[2])
print("".join(a))


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100000)


def main():
    a = deque(input())
    a.pop()

    a_append = a.append
    a_appendleft = a.appendleft

    Q = int(input())
    count = 0
    for _ in range(Q):
        q = list(input().split())
        if q[0] == "1":
            count += 1
        else:
            if count % 2 == 0:
                if q[1] == "1":
                    a_appendleft(q[2])
                else:
                    a_append(q[2])
            else:
                if q[1] == "1":
                    a_append(q[2])
                else:
                    a_appendleft(q[2])

    b = list(a)
    if count % 2 != 0:
        b.reverse()
    print("".join(b))


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

import math

def minus_one(n):
    return n - 1

N, K = map(int, input().split(" "))
# A = list(map(minus_one, list(map(int, input().split(" ")))))

doubling_table = [list(map(minus_one, list(map(int, input().split(" ")))))]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)

### FIXED CODE ###

import math

def minus_one(n):
    return n - 1

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

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)
### BUGGY CODE ###

N,W = list(map(int,input().split()))
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    w_l.append(w)
    v_l.append(v)
def knapsack(N,W,w_l,v_l):
    if (N==0 or W==0):
        return 0
    elif(w_l[N-1]>W):
        return knapsack(N-1,W,w_l,v_l)
    
    return max(knapsack(N-1,W,w_l,v_l), v_l[N-1]+knapsack(N-1,W-w_l[N-1],w_l,v_l))
ans = knapsack(N,W,w_l,v_l)
print(ans)

### FIXED CODE ###

import numpy as np

N,W = list(map(int,input().split()))
dp = np.zeros(W+1,dtype = int)
for i in range(N):
    w,v = list(map(int,input().split()))
    dp[w:] = np.maximum(dp[w:],dp[:-w] + v)
print(dp[-1])