n,k = gets.split.map(&:to_i)
sushi = n.times.map{|i|gets.split.map(&:to_i).push(i)}.sort_by{|i,j,k|-j}
a = Hash.new(0)
n.times do |i|
    a[sushi[i][0]] = sushi[i] if a[sushi[i][0]][1] < sushi[i][1]
end
b = a.values.sort_by{|i,j,k|-j}
def calc(n,k,b,sushi,v)
    ret = 0
    a = Hash.new(false)
    v.times do |i|
        ret += b[i][1]
        a[b[i][2]] = true
    end
    k -= v
    i = 0
    while k > 0
        if !a[sushi[i][2]]
            a[sushi[i][2]] = true
            k -= 1
            ret += sushi[i][1]
        end
        i += 1
    end
    return ret+v*v
end

min = 1
max = b.size
while max-min > 2
    mid1 = (min*2+max)/3
    mid2 = (min+max*2)/3
    if calc(n,k,b,sushi,mid1) > calc(n,k,b,sushi,mid2)
        max = mid2
    else
        min = mid1
    end
end
ans = 0
for i in min..max
    ret = calc(n,k,b,sushi,i)
    ans = ret if ans < ret
end
puts ans