
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
max = 0
for a in answer do
    max += a[:d]
end
counts = counter.size
max += (counts * counts)
once_sum = 0
for os in once do
    once_sum += os[:d]
end
memo = 0
for tw in twice do
    memo += tw[:d]
end

twice.each_index do |i|
    if rest.size > 0 then
        p = rest.shift
        if counter[p[:t]] == 0 then
            counter[p[:t]] += 1
            memo = memo - twice[i][:d] + p[:d]
            twice[i][:t] = p[:t]
            twice[i][:d] = p[:d]
            counts += 1
            sum = once_sum + memo + (counts * counts)
            if max < sum then 
                max = sum
            end
        end
    end
end


puts(max)
