input = STDIN.readline.split()
n = input[0].to_i
k = input[1].to_i
td_list = STDIN.readlines
td_list.map!{|line|line.split()}
hash_list = []
for td in td_list do
    t = td[0]
    d = td[1].to_i
    hash_list.push(Hash[:t, t, :d, d])
end
hash_list.sort! do |a, b|
    a[:d] <=> b[:d]
end
hash_list.reverse!
answer = hash_list[Range.new(0, k, true)]
counter = Hash.new(0)
for td_a in answer do
    counter[td_a[:t]] += 1
end
once = answer.select do |once_td|
    counter[once_td[:t]] == 1
end
twice = answer.select do |twice_td|
    counter[twice_td[:t]] > 1
end
twice.reverse!
rest = hash_list[Range.new(k, n, true)].select do |rest_td|
    counter[rest_td[:t]] == 0
end
answer_d = answer.map{|answer_td|answer_td[:d]}
max = answer_d.sum + (counter.size * counter.size)
twice.each_index do |i|
    if rest.size > 0 && counter[twice[i][:t]] > 0 then
        counter[twice[i][:t]] -= 1
        p = rest.shift
        counter[p[:t]] += 1
        twice[i][:t] = p[:t]
        twice[i][:d] = p[:d]
        sum = (once + twice).map{|ot_td|ot_td[:d]}.sum + (counter.size * counter.size)
        if max < sum then 
            max = sum
        end
    end
end

puts(max)