n, w = gets.split(" ").map(&:to_i)
goods = Array.new(n)
for i in 0..n-1
  goods[i] = gets.split(" ").map(&:to_i)
end

max = 0
v = Array.new(n+1,Array.new(w,0))
for i in 1..n
  for c in 0..w-1
    if c - goods[i-1][1] <= 0
      v[i][c] = v[i-1][c]
    else
      v[i][c] = [v[i-1][c], v[i-1][c-goods[i-1][1]]+goods[i-1][0]].max
    end
    max = [max, v[i][c]].max
  end
end

puts max