n, x = gets.split.map(&:to_i)

toka = []
n.times do
  toka << gets.split.map(&:to_i).reverse
end

if n <= 30
  puts "WA"
  exit
end
#[[weight, happiness], ...]
dp = Array.new(n + 1).map{Array.new(1, [0, 0])}

for i in 0 .. n - 1
  for w in 0 .. x
    #if i == 0 then look at dp[-1][w], dp[-1] = [0, 0, ... , 0]
    if w >= toka[i][0]
      c0 = dp[i - 1].size - 1
      while dp[i - 1][c0][0] > w - toka[i][0]
        c0 -= 1
      end
      last0 = dp[i - 1][c0][1] + toka[i][1]

      c1 = dp[i - 1].size - 1
      while dp[i - 1][c1][0] > w
        c1 -= 1
      end
      last1 = dp[i - 1][c1][1]

    if last1 > last0 && dp[i][-1][1] < last1
      dp[i] << [w, last1]
    elsif last1 < last0 && dp[i][-1][1] < last0
      dp[i] << [w, last0]
    end end end end

puts p[n - 1][-1][1]