# Define Item class
Item = Struct.new(:value, :weight)

def max(a, b)
  a > b ? a : b
end

# Make 2D array
def make_2d_array(n, m, init)
  n.times.map{[init] * m}
end


# Input values
_, W = gets.split(' ').map(&:to_i)
items = []
while line = gets
  v, w = line.split(' ').map(&:to_i)
  items.push(Item.new(v, w))
end


# Create DP table
dp_table = make_2d_array(items.size + 1, W + 1, nil)
# Initialize the first column
dp_table.size.times{|i|
  dp_table[i][0] = 0
}
# Initialize the first row
dp_table[0].size.times{|j|
  dp_table[0][j] = 0
}


# Fill DP table
(1..items.size).each{|i|
  item = items[i-1]
  (1..W).each{|j|
    if 0 <= j - item.weight
      dp_table[i][j] = max(dp_table[i-1][j], dp_table[i-1][j - item.weight] + item.value)
    else
      dp_table[i][j] = dp_table[i-1][j]
    end

  }
}

# Get max weight
max_weight = dp_table[-1][-1]
puts(max_weight)

