local N, K = io.read("n", "n")
local sushi_list = {}
--local sushi_types = {}
for i=1,N do
    local t, d = io.read("n", "n")
    local tuple = {t, d, false} -- 3rd element: used flag
    --local tuple = {t, d}
    sushi_list[i] = tuple
    --if not sushi_types[t] then
    --    sushi_types[t] = {}
    --end
    --table.insert(sushi_types[t], tuple)
end

-- sort order by deliciousness (most tasty sushi first)
table.sort(sushi_list, function (x, y) return x[2] > y[2] end)
--for _,sushi_t in pairs(sushi_types) do
--    table.sort(sushi_t, function (x, y) return x[2] > y[2] end)
--end

-- maximaize base score
local base_score = 0
local used = {}
for i=1,K do
    local tuple = sushi_list[i]
    base_score = base_score + tuple[2]
    if used[tuple[1]] == nil then
        used[tuple[1]] = 0
    end
    used[tuple[1]] = used[tuple[1]] + 1
    tuple[3] = true
end
local not_used_sushis = {}
local not_used_sushis_appeared = {}
for i=K+1,N do
    local tuple = sushi_list[i]
    if used[tuple[1]] == nil then
        if not_used_sushis_appeared[tuple[1]] then
            -- never use this one
        else
            not_used_sushis_appeared[tuple[1]] = true
            table.insert(not_used_sushis, tuple)
        end
    end
end
local ntypes = 0
for k,_ in pairs(used) do
    ntypes = ntypes + 1
end
local bonus_score = ntypes * ntypes
local score = base_score + bonus_score


if false then
    print("maximized base")
    for i,v in ipairs(sushi_list) do
        print(v[1],v[2],v[3])
    end
    print("not used sushis")
    for i,v in ipairs(not_used_sushis) do
        print(v[1],v[2],v[3])
    end
    print("--")
end


-- try increase bonus
local discard_i = K
local take_i = 1
local max_score = score
while true do
    -- discard least tasty one (constraint: keep ntypes)
    local discard_tuple = sushi_list[discard_i]
    if used[discard_tuple[1]] >= 2 then
        used[discard_tuple[1]] = used[discard_tuple[1]] - 1
        local take_tuple = not_used_sushis[take_i]
        take_i = take_i + 1
        local score_temp = (score - discard_tuple[2] + take_tuple[2]) - ntypes * ntypes + (ntypes + 1) * (ntypes + 1)
        if score_temp > max_score then
            max_score = score_temp
        end
        discard_tuple[3] = false
        take_tuple[3] = true
        score = score_temp
        ntypes = ntypes + 1
        if take_i > #not_used_sushis then
            break
        end
    else
        -- keep ntypes
    end
    discard_i = discard_i - 1
    if discard_i == 0 then
        break
    end
end

print(max_score)

