#!/usr/bin/env python3

import sys, os

 

def main():

    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]

    n, m = inp[0],inp[1]

 

    wi, vi = inp[2], inp[3]

 

 

    dp = [0] * (m + 1)

    for j in range(wi, m + 1):

        dp[j] = vi

 

    for i in range(n - 1):

        wi = inp[2*i + 4]

        vi = inp[2*i + 5]

        for j in range(m, wi-1, -1):

            x = vi + dp[j - wi]

            if dp[j] < x:

                dp[j] = x

 

    print((dp[-1]))

main()

#!/usr/bin/env python3

import sys, os

range = xrange



def main():

    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]

    n, m = inp[0],inp[1]

 

    wi, vi = inp[2], inp[3]

 

 

    dp = [0] * (m + 1)

    for j in range(wi, m + 1):

        dp[j] = vi

 

    for i in range(n - 1):

        wi = inp[2*i + 4]

        vi = inp[2*i + 5]

        for j in range(m, wi-1, -1):

            x = vi + dp[j - wi]

            if dp[j] < x:

                dp[j] = x

 

    print((dp[-1]))

main()

#!/usr/bin/env python3
import sys, os


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0], inp[1]
    wi, vi = inp[2], inp[3]
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in range(m, wi - 1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
    print((dp[-1]))


main()

#!/usr/bin/env python3
import sys, os

range = xrange


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0], inp[1]
    wi, vi = inp[2], inp[3]
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in range(m, wi - 1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
    print((dp[-1]))


main()

+ +range = xrange