n, capacity = gets.split.map(&:to_i)
values, weights = n.times.map { gets.split.map(&:to_i) }.transpose

solve = -> {
  dp = Array.new(n+1) { |i|
    Array.new(capacity+1) { |j|
      (i == n) ? 0 : nil
    }
  }

  (n-1).downto(0) do |i|
    0.upto(capacity) do |j|
      if weights[i] > j
        dp[i][j] = dp[i+1][j]
      else
        dp[i][j] = [ dp[i+1][j-weights[i]] + values[i],
                     dp[i+1][j] ].max
      end
    end
  end

  dp[0][capacity]
}

puts solve.()