#方針: 1種類だけ食べるときの最大値、
# 2種類だけ食べるときの最大値、
# 3種類だけ食べるときの最大値・・・を全部求めてmaxを取る

N, K = gets.split.map(&:to_i)

#寿司リストを保持
sushi = Array.new(N){gets.split.map(&:to_i)}

#寿司リストの前処理, 美味しさ順にソート
sushi.sort_by{|x| x[1]}

#sushiに初めて出たかどうかフラグを付与
appeared = []
0.upto(sushi.length-1) do |i|
  if appeared.include?(sushi[i][0])
    sushi[i].push(0)
  else
    sushi[i].push(1)
    appeared.push(sushi[i][0])
  end
end
#食べる寿司セット候補
eaten = sushi[0..K-1]
variety = 0
eaten.each do |s|
  if s[2] == 1
    variety +=1
  end
end

def calc(e,variety)
  oishisa = 0
  e.each do |e|
    oishisa += e[1]
  end
  return oishisa + variety**2
end

#貪欲していく
ans = calc(eaten,variety)

#前からK種類取って評価してansと比較
while variety < appeared.length
  ans = [ans, calc(eaten,variety)].max

  #eatenから種類が減らない範囲で最もおいしさの小さいものを取り除く
  0.upto(eaten.length-1) do |i|
   if eaten[-1-i][2] != 1
      eaten.delete_at(-1-i)
      break
   end
  end

  #sushiから種類を増やせて最もおいしさの大きいものを追加する
  0.upto(sushi.length-1) do |i|
   if sushi[i][2] == 1
     eaten.push(sushi[i])
     variety += 1
     break
   end
  end
end

puts ans