n,t = gets.split.map(&:to_i)
list = (1..n).map{gets.split.map(&:to_i)}
max = 0
(0...n).each{|lastfoodi|
  lastfood = list[lastfoodi]
  newlist = list.dup
  newlist.delete_at(lastfoodi)
  deli = (0..t).map{[0,[]]}
  deli[0] = [0,[newlist]]
  (0...t).each{|ti|
    predeli,left = deli[ti]
    left.each{|l|
      (0...l.size).each{|i|
        newl = l.dup
        eat = newl.delete_at(i)
        newt = ti+eat[0]
        newdeli = predeli+eat[1]
        if newt < t
          max = [max,newdeli+lastfood[1]].max
          if deli[newt][0] == newdeli
            deli[newt][1] << newl
          elsif deli[newt][0] < newdeli
            deli[newt] = [newdeli,[newl]]
          end
        end
      }
    }
  }
}
p max