import std.stdio, std.conv, std.string, std.array, std.math, std.regex, std.range, std.ascii;
import std.typecons, std.functional;
import std.algorithm, std.container;

void scanLine(TList...)(ref TList list)
{
    auto elem = readln.split;
    foreach (i, T; TList)
    {
        list[i] = elem[i].to!T;
    }
}

T[] scanArray(T = long)()
{
    return readln.split.to!(T[]);
}

T scanElem(T = long)()
{
    string res;
    int c = ' ';
    while (isWhite(c) && c!=-1)
    {
        c = getchar;
    }
    while (!isWhite(c) && c!=-1)
    {
        res ~= cast(char)c;
        c = getchar;
    }
    return res.to!T;
}

struct Sushi
{
    long t;
    long d;
}

void main()
{
    const N = scanElem;
    const K = scanElem;
    Sushi[] sushies;
    foreach(i; 0..N)
    {
        Sushi sushi;
        scanLine(sushi.t, sushi.d);
        sushies ~= sushi;
    }
    sushies.sort!"a.d>b.d";

    auto eatTypes = sushies.take(K).map!"a.t".group.assocArray;
    auto eatTypeCount = sushies.take(K).map!"a.t".group.count;
    long eatPoint = sushies.take(K).fold!"a+b.d"(0L);
    long maxPoint = eatPoint+eatTypeCount^^2;
    auto eatHeap = BinaryHeap!(Sushi[], "a.d>b.d")(sushies.take(K));
    foreach(sushi; sushies.drop(K))
    {
        if(sushi.t in eatTypes)
            continue;
        while(!eatHeap.empty && eatTypes[eatHeap.front.t]==1)
        {
            eatHeap.popFront;
        }
        if(eatHeap.empty)
            break;
        auto removeSushi = eatHeap.front; eatHeap.popFront;
        eatHeap.insert(sushi);
        eatTypeCount++;
        eatTypes[sushi.t] = 1;
        eatTypes[removeSushi.t]--;
        eatPoint = eatPoint - removeSushi.d + sushi.d;
        maxPoint = max(maxPoint, eatPoint + eatTypeCount^^2);
    }
    writeln(maxPoint);
}
