input = STDIN.readline.split()
n = input[0].to_i
k = input[1].to_i
td_list = STDIN.readlines.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 in answer do
    counter[td[:t]] += 1
end
final_answer = hash_list[Range.new(0, k, true)].keep_if do |td|
    counter[td[:t]] == 1
end
twice = hash_list[Range.new(0, k, true)].keep_if do |td|
    counter[td[:t]] > 1
end
twice.reverse!
rest = hash_list[Range.new(k, n, true)].keep_if do |td|
    counter[td[:t]] == 0
end
max = answer.map{|td|td[:d]}.sum + (counter.size ** 2)
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 = (final_answer + twice).map{|td|td[:d]}.sum + (counter.size ** 2)
        if max < sum then 
            max = sum
        end
    end
end

puts(max)