ns, *_tds = ARGF.read.split("\n").map { |e| e.split }
n, nk = ns.map { |e| e.to_i }
tds = _tds.map { |e| e.map { |e| e.to_i } }
_h = {}
tds.map { |e|
  k, d = e
  _h[k] = [] if _h[k].nil?
  _h[k] << d
}
h = {}
_h.map { |k, v|
  h[k] = v.sort
}
knum = h.keys.length
costs = {}
point = (knum ** 2 - (knum - 1) ** 2)
h.map { |k, v|
  if v.length == 1
    costs[k] = [point + v.first, v]
  else
    costs[k] = [v.first, v]
  end
}
(n - nk).times {
  # p costs
  k = costs.keys.min { |a, b| costs[a].first <=> costs[b].first }
  # p k
  costs[k].last.shift
  if costs[k].last.length == 0
    costs.delete k
    knum -= 1
    point = (knum ** 2 - (knum - 1) ** 2)
  elsif costs[k].last.length == 1
    x, y = costs[k]
    costs[k] = [point + y.first, y]
  else
    x, y = costs[k]
    costs[k] = [y.first, y]
  end
}
# p costs
# p costs.keys.length
cost = costs.keys.length ** 2
# p costs.keys
costs.map { |k, e|
  v = e.last
  cost += v.reduce(0) { |acc, e| acc + e }
}
puts cost
