from collections import Counter,defaultdict

import sys,bisect,math,itertools,string,queue

mod = 10**9+7

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpl_str(): return list(sys.stdin.readline().split())



n,w = inpl()

ww = [0] * n

vv = [0] * n

for i in range(n):

    ww[i],vv[i] = inpl()

dp = [[0 for i in range(w+1)] for j in range(n+1)]



for i in range(n):

    for j in range(w+1):

        if j >= ww[i]:

            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])

        else:

            dp[i+1][j] = dp[i][j]

print((dp[n][w]))





            

from collections import Counter,defaultdict,deque

from heapq import heappop,heappush,heapify

import sys,bisect,math,itertools,fractions,pprint

sys.setrecursionlimit(10**8)

mod = 10**9+7

mod2 = 998244353

INF = float('inf')

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))



n,w = inpl()

wei = [0] * n

val = [0] * n

for i in range(n):

    wei[i],val[i] = inpl()



dp = [[0]*(w+5) for i in range(n+5)]

for i in range(n):

    for j in range(w+1):

        if wei[i] > j:

            dp[i+1][j] = dp[i][j]

            continue

        dp[i+1][j] = max(dp[i+1][j], dp[i][j-wei[i]]+val[i], dp[i][j])

print((dp[n][w]))
from collections import Counter, defaultdict
import sys, bisect, math, itertools, string, queue

mod = 10**9 + 7


def inp():
    return int(sys.stdin.readline())


def inpl():
    return list(map(int, sys.stdin.readline().split()))


def inpl_str():
    return list(sys.stdin.readline().split())


n, w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i], vv[i] = inpl()
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j >= ww[i]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - ww[i]] + vv[i])
        else:
            dp[i + 1][j] = dp[i][j]
print((dp[n][w]))

from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, pprint

sys.setrecursionlimit(10**8)
mod = 10**9 + 7
mod2 = 998244353
INF = float("inf")


def inp():
    return int(sys.stdin.readline())


def inpl():
    return list(map(int, sys.stdin.readline().split()))


def inpln(n):
    return list(int(sys.stdin.readline()) for i in range(n))


n, w = inpl()
wei = [0] * n
val = [0] * n
for i in range(n):
    wei[i], val[i] = inpl()
dp = [[0] * (w + 5) for i in range(n + 5)]
for i in range(n):
    for j in range(w + 1):
        if wei[i] > j:
            dp[i + 1][j] = dp[i][j]
            continue
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - wei[i]] + val[i], dp[i][j])
print((dp[n][w]))

-from collections import Counter, defaultdict -import sys, bisect, math, itertools, string, queue +from collections import Counter, defaultdict, deque +from heapq import heappop, heappush, heapify +import sys, bisect, math, itertools, fractions, pprint +sys.setrecursionlimit(10**8) +mod2 = 998244353 +INF = float("inf") -def inpl_str(): -    return list(sys.stdin.readline().split()) +def inpln(n): +    return list(int(sys.stdin.readline()) for i in range(n)) -ww = [0] * n -vv = [0] * n +wei = [0] * n +val = [0] * n -    ww[i], vv[i] = inpl() -dp = [[0 for i in range(w + 1)] for j in range(n + 1)] +    wei[i], val[i] = inpl() +dp = [[0] * (w + 5) for i in range(n + 5)] -        if j >= ww[i]: -            dp[i + 1][j] = max(dp[i][j], dp[i][j - ww[i]] + vv[i]) -        else: +        if wei[i] > j: +            continue +        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - wei[i]] + val[i], dp[i][j])