def nap(n,cap):

    val = [0]*(cap+1)

    for _ in range(n):

        w,v = list(map(int,input().split()))

        for k in range(cap,w-1,-1):

            nv=val[k-w]+v

            if val[k]<nv:

                val[k]=nv

    return max(val)



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

print((nap(n,cap)))

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

dp=[[0]*(m+1) for _ in range(n+1)]



for i in range(1,n+1):

    w,v=list(map(int,input().split()))

    dp[i][w]=max(dp[i-1][w],v)

    for j in range(m+1):

        if dp[i-1][j]==0:

            continue

        if j+w<=m:

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



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





print((max(dp[n])))

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for k in range(cap, w - 1, -1):
            nv = val[k - w] + v
            if val[k] < nv:
                val[k] = nv
    return max(val)


n, cap = list(map(int, input().split()))
print((nap(n, cap)))

n, m = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = list(map(int, input().split()))
    dp[i][w] = max(dp[i - 1][w], v)
    for j in range(m + 1):
        if dp[i - 1][j] == 0:
            continue
        if j + w <= m:
            dp[i][j + w] = max(dp[i][j + w], dp[i - 1][j] + v)
        dp[i][j] = max(dp[i - 1][j], dp[i][j])
print((max(dp[n])))

-def nap(n, cap): -    val = [0] * (cap + 1) -    for _ in range(n): -        w, v = list(map(int, input().split())) -        for k in range(cap, w - 1, -1): -            nv = val[k - w] + v -            if val[k] < nv: -                val[k] = nv -    return max(val) - - -n, cap = list(map(int, input().split())) -print((nap(n, cap))) +n, m = list(map(int, input().split())) +dp = [[0] * (m + 1) for _ in range(n + 1)] +for i in range(1, n + 1): +    w, v = list(map(int, input().split())) +    dp[i][w] = max(dp[i - 1][w], v) +    for j in range(m + 1): +        if dp[i - 1][j] == 0: +            continue +        if j + w <= m: +            dp[i][j + w] = max(dp[i][j + w], dp[i - 1][j] + v) +        dp[i][j] = max(dp[i - 1][j], dp[i][j]) +print((max(dp[n])))