# Your code here!
N,C = gets.split.map(&:to_i)
weight = []
V = []
N.times{
    x  = gets.split.map(&:to_i)
    V << x[0]
    weight << x[1]
}

dp = Array.new(N+1).map{Array.new(C+1,0)}

N.times{|i|
    (C+1).times{|w|
        if w >= weight[i]
            dp[i+1][w] = [dp[i][w],dp[i][w-weight[i]]+V[i]].max
        else
            dp[i+1][w] = dp[i][w]
        end
    }
}

puts dp[N][C]
