def max(a,b)
  if a<b
    return b
  else
    return a
  end
end

n,w=gets.chomp.split(/ /).map{|i| i.to_i}
vi=Array.new(n+1)
wi=Array.new(n+1)
for i in 1..n
  vi[i],wi[i]=gets.chomp.split(/ /).map{|i| i.to_i}
end
d=Array.new(n+1).map{Array.new(w+1,0)}
for i in 0..w
  d[0][i]=0
end
for i in 0..n
  d[i][0]=0
end
for i in 1..n
  for j in 1..w
    if j>=wi[i]
      d[i][j]=max(d[i-1][j-wi[i]]+vi[i],d[i-1][j])
    else
      d[i][j]=d[i-1][j-1]
    end
    print "d[#{i}][#{j}]=",d[i][j],"\n"
  end
end
print d[n][w],"\n"