n, k = gets.chomp.split.map(&:to_i)
ary = []
n.times do
  ary << gets.chomp.split.map(&:to_i)
end
# とりあえずsum(select_sushi.おいしさ)のmaxを取り、かぶっている寿司を変えて比較
# かぶっている寿司が複数ある時の処理に注意
ary.sort! {|a,b| b[1] <=> a[1]}
tmp_ans = 0
neta = {}
# 複数はいっているものをindex管理
check = []
k.times do |i|
  tmp_ans += ary[i][1]
  if neta[ary[i][0]]
    neta[ary[i][0]] += 1
    check << i
  else
    neta[ary[i][0]] = 1
  end
end
tmp_ans += (neta.length)**2
# 
# p neta
# p tmp_ans
# p check

ans = tmp_ans + 0

# ここからかぶりをなくす
end_sushi = k-1
while check.length != 0
  # 今使ってないネタで一番大きいのと一番下っ端を交換
  j = 0
  flag = false
  while true
    if k+j == n
      # つまりなかったかk == n
      flag = true
      break
    end
    if !neta[ary[k+j][0]]
      tuika = ary[k+j][1]
      neta[ary[k+j][0]] = 1
      # neta[ary[check[-1]][0]] -= 1
      break
    end
    j += 1
  end
  if flag
    break
  end
  # p tmp_ans.class
  # p neta.length
  # p tuika
  # p ary[check[-1]][1]
  now_ans = tmp_ans - ary[check[-1]][1] + tuika + (2 * neta.length - 1)
  # now_ans = tmp_ans - ary[check[-1][1]] + tuika
  check.pop
  # p [tmp_ans, now_ans]
  ans = [ans, now_ans].max
  k += 1
end
puts ans
