local mma, mmi = math.max, math.min
local n, k = io.read("*n", "*n")
local sushi = {}
local neta = {}
for i = 1, n do
  sushi[i] = {}
  local t, d = io.read("*n", "*n")
  sushi[i].t, sushi[i].d = t, d
  neta[t] = true
end
local total_neta_cnt = 0
for z, v in pairs(neta) do total_neta_cnt = total_neta_cnt + 1 end
local lim_neta_cnt = mmi(total_neta_cnt, k)
table.sort(sushi, function(a, b) return a.d > b.d end)

local num_per_neta = {}
local cur_neta_cnt = 0
local score_d = 0
for i = 1, k do
  score_d = score_d + sushi[i].d
  local t = sushi[i].t
  if not num_per_neta[t] then
    cur_neta_cnt = cur_neta_cnt + 1
    num_per_neta[t] = 1
  else
    num_per_neta[t] = num_per_neta[t] + 1
  end
end
local optimal_score = score_d + cur_neta_cnt * cur_neta_cnt

local add_start_pos = k + 1
local remove_start_pos = k
while cur_neta_cnt < lim_neta_cnt do
  while num_per_neta[sushi[add_start_pos].t] do
    add_start_pos = add_start_pos + 1
  end
  cur_neta_cnt = cur_neta_cnt + 1
  num_per_neta[sushi[add_start_pos].t] = 1
  score_d = score_d + sushi[add_start_pos].d
  add_start_pos = add_start_pos + 1
  while num_per_neta[sushi[remove_start_pos].t] == 1 do
    remove_start_pos = remove_start_pos - 1
  end
  num_per_neta[sushi[remove_start_pos].t] = num_per_neta[sushi[remove_start_pos].t] - 1
  score_d = score_d - sushi[remove_start_pos].d
  remove_start_pos = remove_start_pos - 1
  optimal_score = mma(optimal_score, score_d + cur_neta_cnt * cur_neta_cnt)
end
print(optimal_score)
