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

N = int(input())
d = list(map(int, input().split()))
ans = 0

K = 1
while max(d) >= K:
    abc = []
    arc = []
    for i in d:
        if i >= K:
            arc.append(i)

        else:
            abc.append(i)
    if len(abc) == len(arc):
        ans += 1
    K += 1
print(ans)


### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))
d.sort()

print(d[N//2]-d[N//2-1])
### BUGGY CODE ###

N=int(input())
A=[]

for i in range(N):
  A.append(int(input()))

for j in range(N):
  if j == A.index(max(A)) and A.count(max(A)) == 1:
    B=[i for i in A if i != max(A)]
    print(max(B))
  else:
    print(max(A))

### FIXED CODE ###

N=int(input())
A=[]

for i in range(N):
  A.append(int(input()))
B=sorted(A)
B=B[:len(B)-1]
C=[max(A)]*N
C[A.index(max(A))]=max(B)
for j in range(N):
  print(C[j])
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int, input().split())))

tri = []
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if abs(L[i] - L[j]) < L[k] < L[i] + L[j]:
                tri.append((L[i], L[j], L[k]))

print(len(set(tri)))


### FIXED CODE ###

import bisect

n = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

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

s = input()
q = int(input())

for i in range(q):
    query = input()
    if query[0] == '1':
        s = s[::-1]
    else:
        query = query.split()
        if query[1] == '1':
            s = query[2] + s
        else:
            s = s + query[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

ok = True
for i in range(q):
    query = input()
    if query[0] == '1':
        if ok:
            ok = False
        else:
            ok = True
    else:
        query = query.split()
        if ok:
            if query[1] == '1':
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if query[1] == '1':
                s.append(query[2])
            else:
                s.appendleft(query[2])
if not ok:
    s.reverse()
print(''.join(list(s)))
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())

s = []
print(0, flush=True)
s.append(input())
if s[-1] == 'Vacant':
    exit()

l, r = 0, N
while r - l > 2:
    m = (l + r) // 2
    print(m, flush=True)
    s.append(input())
    if s[-1] != 'Vacant':
        exit()

    if s[i - 1] == s[i]:
        l, r = (l, m) if (m - l) % 2 == 1 else (m, r)
    else:
        l, r = (m, r) if (m - l) % 2 == 1 else (l, m)
print(m + 1, flush=True)


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###

N = int(input())
a = list(input().split())
s = [a.index(str(i))+1 for i in range(1,N+1)]
result = " ".join(map(str, s))
print(result)


### FIXED CODE ###


N = int(input())
a = list(map(int, input().split()))
s = [-1]
s.extend(0 for _ in range(N))

for i, item in enumerate(a):
    s[item] = i+1

result = " ".join(map(str, s[1:]))
print(result)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# room_connection = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     room_connection[a - 1].append(b - 1)
#     room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in range(N):
        if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
counter = 0
# R, G, B = sorted([R, G, B])
r = 0
while r * R <= N:
  g = 0
  while g * G <= N:
    b = (N - r*R - g*G)/B 
    if b < 0:
      break
    elif b == int(b):
      counter += 1
    g += 1
  r += 1
print(counter)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
counter = 0
if R < G:
  R, G = G, R
if G < B:
  G, B = B, G
if R < G:
  R, G = G, R
r = 0
while r * R <= N:
  g = 0
  if B == 1:
    counter += (N - r*R)//G + 1
    r += 1
    continue
  while g * G <= N:
    b = (N - r*R - g*G)/B 
    if b < 0:
      break
    elif b == int(b):
      counter += 1
    g += 1
  r += 1
print(counter)
### BUGGY CODE ###

import os

def main():
	num = int(input())
	list_num = list(map(int, input().split()))
	flag = False
	for i,v in enumerate(list_num):
		if v in list_num[i+1:]:
			flag = True
			break

	if flag:
		print("NO")
	else:
		print("YES")	

if __name__ == "__main__":
	main()


### FIXED CODE ###

import os

def main():
	num = int(input())
	list_num = set(map(int, input().split()))
	if len(list_num) != num:
		print("NO")
	else:
		print("YES")

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

s=input()
        
ans=0
for i in range(5,len(s)):
    for j in range(len(s)-i+1):
         if int(s[j:j+i])%2019==0:
            ans+=1

print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

x1 = input()
x2 = [int(s) for s in input().strip().split(" ") ]
 
result =  1
for x in x2:
  result *= x 

if 10**18 < result :
  result = -1

print(result) 


### FIXED CODE ###

x1 = input()
x2 = [int(i) for i in input().split(" ")]

result = 0
if 0 in x2:
  None 
else:
  result = 1
  for xv in x2:
     result = xv * result
  
     if 10**18 < result : 
        result = -1
        break


print(result)
### BUGGY CODE ###

import numpy as np
def code(n,p):
    mins = []
    for idx in range(1,len(p)+1):
        mins.append(np.min(p[:idx]))
        
    
    return sum(np.array(mins)==p)

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

idx = code(n,p)
if idx == None:
    print(n)
else:
    print(idx)


### FIXED CODE ###

n=int(input())
plist = list(map(int,input().split()))
cnt = 0
pmax=plist[0]
for i in range(n):
    if plist[i]<=pmax:
        pmax=plist[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=6400:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

N=int(input())
S = [''.join(sorted(input())) for i in range(N)]
ans=0
for elem in set(S):
    sum_ = sum([s==elem for s in S])
    ans += sum_*(sum_-1)//2
print(ans)

### FIXED CODE ###

import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        if c > L:
            continue
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    Q, *ST = map(int, read().split())

    dist = [[(INF, INF)] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = (0, 0)
        hq = [(0, 0, i)]
        while hq:
            refuel, used, v = heappop(hq)
            if dist[i][v] < (refuel, used):
                continue
            for nv, cost in G[v]:
                if used + cost <= L:
                    if dist[i][nv] > (refuel, used + cost):
                        dist[i][nv] = (refuel, used + cost)
                        heappush(hq, (refuel, used + cost, nv))
                else:
                    if dist[i][nv] > (refuel + 1, cost):
                        dist[i][nv] = (refuel + 1, cost)
                        heappush(hq, (refuel + 1, cost, nv))

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        ans[i] = dist[s - 1][t - 1][0] if dist[s - 1][t - 1][0] != INF else -1

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    Q, *ST = map(int, read().split())

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    H = [[INF] * N for _ in range(N)]
    for i in range(N - 1):
        for j in range(i + 1, N):
            if G[i][j] <= L:
                H[i][j] = H[j][i] = 1

    for i in range(N):
        H[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if H[i][j] > H[i][k] + H[k][j]:
                    H[i][j] = H[i][k] + H[k][j]

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        s -= 1
        t -= 1
        if H[s][t] == INF:
            ans[i] = -1
        else:
            ans[i] = H[s][t] - 1

    print(*ans, sep='\n')
    return


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

a, b, c, d = [int(i) for i in input().split()]
n = {i for i in range(a, b+1) if i % c != 0 and i % d != 0}
ans = len(n)
print(ans)

### FIXED CODE ###

import fractions


def anti_division(n, d1, d2):
    g = fractions.gcd(d1, d2)
    l = (d1 * d2) // g
    ret = n - (n//d1 + n//d2) + n//l
    return ret


a, b, c, d = [int(i) for i in input().split()]
ans = anti_division(b, c, d) - anti_division(a - 1, c, d)
print(ans)
### BUGGY CODE ###

a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        if n > x:
            n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
def func2():
    for i in range(a):
        s = list(b)
        s[i] = "0" if s[i] == "1" else "1"
        c = "".join(s)
        print(str(func(c)))
func2()

### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
### BUGGY CODE ###

start, end, div = input().strip().split()

count = 0
for i in range(int(start),int(end)+1):
  if i % int(div) == 0:
    count += 1
print(count)

### FIXED CODE ###

start, end, div = list(map(int, input().strip().split()))

count = end // div - start //div

if start % div == 0:
  count += 1
print(count)
### BUGGY CODE ###

import sys
N=int(input())
H=list(map(int,input().split()))
if N==1:
  print('Yes')
else:
  for i in range(N-1):
    if H[i]<=H[i+1]:
      pass
    elif H[i]-H[i+1]==1:
      H[i]-=1
      M=max(H)
      if M-H[i]<=0:
        print('No')
        sys.exit()
      else:
        pass
    elif H[i]-H[i+1]>=2:
      print('No')
      sys.exit()
  print('Yes')

### FIXED CODE ###

import sys
N=int(input())
H=list(map(int,input().split()))
if N==1:
  print('Yes')
else:
  M=1
  for i in range(N-1):
    M=max(M,H[i])
    if H[i]<=H[i+1]:
      pass
    elif H[i]-H[i+1]==1:
      H[i]-=1
      if M-H[i]>1:
        print('No')
        sys.exit()
      else:
        pass
    elif H[i]-H[i+1]>=2:
      print('No')
      sys.exit()
  print('Yes')
### BUGGY CODE ###

def check(r,c):
    return True if B == [i[c:c+C] for i in A[r:r+R]] else False

H,W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
R,C = [int(i) for i in input().split()]
B = [input() for _ in range(R)]

for r in range(H-R+1):
    for c in range(W-C+1):
        if check(r,c):
            print(r,c)


### FIXED CODE ###

from collections import deque
import re
import sys
sys.setrecursionlimit(100000)

class AC:
    
    def __init__(self,num,parent,char):
        self.num = num
        self.parent = parent
        self.char = char
        self.d = {}
        self.failure = None
        
    def insert(self,string,num):
        if not string[0] in self.d:
            self.d[string[0]] = AC(num,self,string[0])
            num+=1
        if not string[1:] == "":
            return self.d[string[0]].insert(string[1:],num)
        else:
            return num
        
    def setFailure(self):
        tmp = self.parent.failure
        while(True):
            if self.char in tmp.d:
                self.failure = tmp.d[self.char]
                break
            else:
                if tmp.num == 0:
                    self.failure = tmp
                    break
                else:
                    tmp = tmp.failure
    
    def setFailureRoot(self):
        self.failure = self
    
    def setFailureFirstLayer(self):
        self.failure = self.parent
       
    def transition(self,string):
        if string == "":
            return []
        elif string[0] in self.d:
            tmp = self.d[string[0]]
            num = "{0:09d}".format(tmp.num) 
            return [num]+tmp.transition(string[1:])
        else:
            if self.num == 0:
                num = "{0:09d}".format(self.num)
                return [num]+self.transition(string[1:])
            else:
                return self.failure.transition(string)
    
H,W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
R,C = [int(i) for i in input().split()]
B = [input() for _ in range(R)]

root = AC(0,None,"")
root.setFailureRoot()
num=1
for i in B:
    num = root.insert(i,num)
d = deque()
for i in root.d.values():
    i.setFailureFirstLayer()
    for j in i.d.values():
        d.appendleft(j)
while(len(d)>0):
    tmp = d.pop()
    tmp.setFailure()
    for i in tmp.d.values():
        d.appendleft(i)
        
trans = ["" for i in range(W)]
for i in A:
    tmp = root.transition(i)
    for j,k in enumerate(tmp):
        trans[j] = trans[j]+k+"#"

ans=""
for i in B:
    ans = ans+root.transition(i)[-1]+"#"

ansd = deque()
for i,j in enumerate(trans):
    obj = re.search(ans,j)
    c = 0
    while(obj):
        s = obj.start()
        if (i-C+1)<0:
            print(i)
        ansd.append(((c+s)//10,i-C+1))
        obj = re.search(ans,j[c+s+10:])
        c += s+10

for i in sorted(ansd):
    print(i[0],i[1])
### BUGGY CODE ###

#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-.py
#
import collections

n = int(input())
l = [str(input()) for i in range(n)]
# l = ["beat", "vet", "beet", "bed", "vet", "bet", "beet"]
c = collections.Counter(l)
number_of_words = len(c)
ans_before_sort = [c.most_common()[0][0]]

for i in range(number_of_words-1):
    if c.most_common()[i][1] == c.most_common()[i+1][1]:
        ans_before_sort.append(c.most_common()[i+1][0])
    else:
        break

ans_after_sort = sorted(ans_before_sort)
print('\n'.join(ans_after_sort))


### FIXED CODE ###

#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-.py
#
import collections

n = int(input())
l = [str(input()) for i in range(n)]
# l = ["beat", "vet", "beet", "bed", "vet", "bet", "beet"]
c = collections.Counter(l)
number_of_words = len(c)
counted_list = c.most_common()
ans_before_sort = [counted_list[0][0]]

for i in range(number_of_words-1):
    if counted_list[i][1] == counted_list[i+1][1]:
        ans_before_sort.append(counted_list[i+1][0])
    else:
        break

ans_after_sort = sorted(ans_before_sort)
print('\n'.join(ans_after_sort))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  # dp[i+1][j] iまでで最大化
  for i in range(n):
    for j in range(W+1):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])

  return dp[n][W]

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

      else:
        dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

  return dp[0][W]

# main()
print(main())