#!/usr/bin/env ruby

@n, @w = gets.split(' ').map &:to_i
@items = []
@n.times.each do
  v, w = gets.split(' ').map &:to_i
  @items << {v: v, w: w}
end

# ans_map[i][w]
# i: 0..i番目のitemまで含めた状態での最大価値
# w: i番目において、各重量での最大価値
@ans_map = []
(0...@n).each do |i|
  (0..@w).each do |j|
    @ans_map[i] ||= []
    @ans_map[i][j] = 0
  end
end

def calc(i)
  item = @items[i]
  if i == 0
    @ans_map[i][item[:w]] = item[:v]
    return
  end

  (0..@w).each do |j|
    if j - item[:w] < 0
      @ans_map[i][j] = @ans_map[i-1][j]
      next
    end
    c1 = @ans_map[i-1][j-item[:w]] + item[:v]
    c2 = @ans_map[i-1][j]
    @ans_map[i][j] = c1 > c2 ? c1 : c2
  end
end

(0...@n).each do |i|
  calc(i)
end

puts @ans_map[@n-1].max

