input = STDIN.read.split("\n").map{|l| l.split(" ").map{|a| a.to_i}}

f = input.shift

N = f[0]
K = f[1]

su = input
su = su.sort_by{|s| s[1]}.reverse

cnt = 0
dp = 0
vc = 0
vd = {}

stack = []
pendings = []

su.each{|s|
    break if cnt >= K
    v = s[0]
    if !vd.has_key?(v)
        stack.push(s[1])
        dp = dp + s[1]
        vc = vc + 1
        cnt = cnt + 1
        vd[v] = true
    else
        pendings.push(s[1])
    end
}

while pendings.length > 0 && (dp + vc * vc) < (dp - stack.last + pendings[0] + (vc - 1) * (vc -1 ))
    vc = vc - 1
    dp = dp - stack.pop + pendings.shift
end

puts dp + vc * vc