if __name__ == '__main__':

    fin=open("rucsac.in","r")
    fout=open("rucsac.out","w")

    lines=fin.readlines()
    line=lines[0]
    line=line.split()
    n=int(line[0])
    G=int(line[1])

    dp=[[0 for j in range(G+1)]for i in range(n+1)]

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

        line=lines[i]
        line=line.split()
        wi=int(line[0])
        value=int(line[1])

        for j in range(0,G+1):

            dp[i][j]=dp[i-1][j]
            if j>=wi:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+value)



    fout.write(str(dp[n][G]))