n,k = gets.split.map(&:to_i)
a = n.times.map{|i|gets.split.map(&:to_i).push(i)}.sort_by{|i,j,k|-j}
v = 0
ans = 0
ret = 0
used = Hash.new(-1)
for i in 0..k-1
    ans += a[i][1]
    if used[a[i][0]] == -1
        v += 1
        used[a[i][0]] = a[i][2]
    end
end
ans += v**2
l = k-1
ret = ans
for i in k..n-1
    if used[a[i][0]] == -1
        while used[a[l][0]] == a[l][2]
            l -= 1
        end
        break if l < 0
        used[a[l][0]] = a[l][2]
        ret += a[i][1]-a[l][1]+2*v+1
        v += 1
        l -= 1
    end
    ans = ret if ans < ret
end
puts ans