class VW
  attr_reader :value, :weight
  def initialize(value, weight)
    @value = value
    @weight = weight
  end
  def to_s
    "V:#{@value} W:#{@weight}"
  end
end

# メモ化再帰での実装
# https://www.slideshare.net/iwiwi/ss-3578511
class MemoizeRecursive
  def main
    @n, upper_w = gets.split.map(&:to_i)

    @ks = Array.new(@n)
    @n.times do |i|
      # [Value, Weight]
      @ks[i] = VW.new(*gets.split.map(&:to_i))
    end
    # pp knapsacks

    # @memoの方でdoneを兼ねられるので省略
    # @done = Array.new(@n) { Array.new(upper_w+1, false) }
    # 既に求めた最大価値を格納（未計算はnil）
    @memo = Array.new(@n) { Array.new(upper_w+1) }

    ans = search(0, upper_w)
    puts ans

    # pp @memo
  end

  def search(i, upper_w)
    return 0 if @n <= i

    # 既に計算済みの場合はそれを返す
    # return @memo[i][upper_w] if @done[i][upper_w]
    return @memo[i][upper_w] unless @memo[i][upper_w].nil?

    item = @ks[i]
    # この品物は入らないので次に進む
    return search(i+1, upper_w) if upper_w < item.weight

    # この品物を入れない場合と入れる場合の両方で探索
    value1 = search(i+1, upper_w)
    value2 = search(i+1, upper_w - @ks[i].weight) + @ks[i].value
    value = [value1, value2].max
    # @done[i][upper_w] = true
    @memo[i][upper_w] = value
    value
  end
end

if __FILE__ == $0
  MemoizeRecursive.new.main
end

