N , K = gets.split.map!{|n| n.to_i}
t = Array.new(N)

for i in 1..N
    t[i-1] = gets.split.map!{|n| n.to_i}
end

t = t.sort{|a , b| -a[1] <=> -b[1]}

max = 0
variety = Hash.new(0)
t.each_with_index do |value , index|
    if index >= K
        break
    end
    
    value[2] = variety[value[0]]
    variety[value[0]] += 1
    max += value[1]
end

max += variety.size ** 2
a = max

for i in 1..K
    if t[K-i][2] == 0
        next
    end

    while K < t.size && variety[t[K][0]] != 0
        t.delete_at(K)
    end

    if K >= t.size
        break
    end

    a += t[K][1] - t[K-i][1] + 2 * variety.size + 1
    if max < a
        max = a 
    end
    variety[t[K][0]] += 1

end

puts max