n, k = gets.strip.split.map(&:to_i)
ss = []
n.times do
  ss << gets.strip.split.map(&:to_i)
end

pt_max = -1
for cs in (0...n).to_a.combination(k)
  pt = 0
  kinds = {}
  for c in cs do
    kinds[ss[c][0]] = true
    pt += ss[c][1]
  end
  pt += kinds.size*kinds.size
  if pt > pt_max then
    pt_max = pt
  end
end

puts pt_max