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
}
(n - nk).times {
  knum = h.keys.length
  k, _ = h.map { |k, v|
    if v.length == 1
      [k, (knum ** 2 - (knum - 1) ** 2) + v.first]
    else
      [k, v.first]
    end
  }.min { |a, b| a.last <=> b.last }
  h[k].shift
  if h[k].length == 0
    h.delete k
  end
}
# p h
# p h.keys.length
cost = h.keys.length ** 2
h.map { |k, v|
  cost += v.reduce(0) { |acc, e| acc + e }
}
puts cost
