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,deque

from heapq import heappop,heappush,heapify

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

sys.setrecursionlimit(10**8)

mod = 10**9+7

INF = float('inf')

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

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



n,W = inpl()

wv = [inpl() for _ in range(n)]

dp = [0] * (W+1)

for i in range(n):

    w,v = wv[i]

    for j in range(w,W+1)[::-1]:

        dp[j] = max(dp[j], dp[j-w] + v)

print((dp[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, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, pprint

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


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


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


n, W = inpl()
wv = [inpl() for _ in range(n)]
dp = [0] * (W + 1)
for i in range(n):
    w, v = wv[i]
    for j in range(w, W + 1)[::-1]:
        dp[j] = max(dp[j], dp[j - w] + v)
print((dp[W]))

-mod2 = 998244353 -def inpln(n): -    return list(int(sys.stdin.readline()) for i in range(n)) - - -n, w = inpl() -wei = [0] * n -val = [0] * n +n, W = inpl() +wv = [inpl() for _ in range(n)] +dp = [0] * (W + 1) -    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])) +    w, v = wv[i] +    for j in range(w, W + 1)[::-1]: +        dp[j] = max(dp[j], dp[j - w] + v) +print((dp[W]))