if __name__=="__main__":
    n,v = [int(x) for x in input().split()]
    w = []
    vs = []
    while n:
        temp_w,temp_v = [int(x) for x in input().split()]
        w.append(temp_w)
        vs.append(temp_v)
        n-=1

    dp = [[0 for x in range(0, v+1)] for x in range(0,len(w)+1)]

    for i in range(1,len(w)+1):
        for j in range(0, v+1):
            if j==0:
                dp[i][j]=0
            else:
                if j < w[i-1]:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+vs[i-1])

    print(dp[len(w)][v])