#二维dp
N = 1010
#定义价值，体积和状态转化数组
#f[i][j]表示从i个物品中选择体积不超过j的物品，所得到的最大收益
w,v,f = [0 for i in range(N)],[0 for i in range(N)],[[0 for i in range(N)]for i in range(N)]

if __name__ == "__main__":
    n,m = map(int,input().split())
    #读入第i件物品的体积和质量
    for i in range(1,n+1):
        v1,w1 = map(int,input().split())
        v[i],w[i] =v1,w1
    for i in range(1,n+1):
        for j in range(1,m+1):
            #不选择第i件物品显然下列式子成立
            f[i][j] = f[i-1][j]
            #如果背包容积大于等于物品的容积，则第i个物品可以加入进去，但是需要选择一个优秀解
            if j >= v[i]:
                f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])
    #即从n个物品中选择体积小于m的最大收益
    print(f[n][m])

#一维dp
N = 1010
#定义价值，体积和状态转化数组
#f[j]选择体积不超过j的物品，所得到的最大收益
w,v,f = [0 for i in range(N)],[0 for i in range(N)],[0 for i in range(N)]

if __name__ == "__main__":
    n,m = map(int,input().split())
    #读入第i件物品的体积和质量
    for i in range(1,n+1):
        v1,w1 = map(int,input().split())
        v[i],w[i] =v1,w1
    for i in range(1,n+1):
        j = m
        #j从最大开始遍历才能确保不会遗漏
        while j >= v[i]:
            #如果背包容积大于等于物品的容积，则第i个物品可以加入进去，但是需要选择一个优秀解
            f[j] = max(f[j],f[j-v[i]]+w[i])
            j -= 1
    #即从n个物品中选择体积小于m的最大收益
    print(f[m])

#简化一维dp（边读入数据，边dp）
N = 1010
#定义价值，体积和状态转化数组
#f[j]选择体积不超过j的物品，所得到的最大收益
f = [0 for i in range(N)]

if __name__ == "__main__":
    n,m = map(int,input().split())
    for i in range(1,n+1):
        v1,w1 = map(int,input().split())
        j = m
        #j从最大开始遍历才能确保不会遗漏
        while j >= v1:
            #如果背包容积大于等于物品的容积，则第i个物品可以加入进去，但是需要选择一个优秀解
            f[j] = max(f[j],f[j-v1]+w1)
            j -= 1
    #即从n个物品中选择体积小于m的最大收益
    print(f[m])