import std.stdio, std.range, std.conv, std.string, std.array;
import std.algorithm.comparison, std.algorithm.iteration, std.algorithm.mutation, std.algorithm.searching, std.algorithm.setops, std.algorithm.sorting;

struct Sushi{
    long id;
    long point;
}
void main()
{
    auto Input = readln().strip.split.to!(long[]);
    const N = Input[0];
    const K = Input[1];
    Sushi[] sushies;
    foreach(i; 0..N)
    {
        Input = readln().strip.split.to!(long[]);
        sushies ~= Sushi(Input[0], Input[1]);
    }

    long idCount;
    Sushi[] eatSushies;
    eatSushies.length = N+1;

    for(int i = 0;i < sushies.length;i++)
    {
        const sushi = sushies[i];
        if(eatSushies[sushi.id].point==0)
        {
            eatSushies[sushi.id] = sushi;
            sushies[i] = sushies[$-1];
            sushies.length--;
            i--;
            idCount++;
        }else if(eatSushies[sushi.id].point < sushi.point)
        {
            const temp = eatSushies[sushi.id];
            eatSushies[sushi.id] = sushi;
            sushies[i] = temp;
        }
    }

    sushies.sort!"a.point>b.point";
    eatSushies = eatSushies.filter!"a.id!=0".array;

    foreach(i; eatSushies.length..K)
    {
        eatSushies ~= sushies[0];
        sushies = sushies[1..$];
    }
    eatSushies.sort!"a.point<b.point";

    for(int i;i < eatSushies.length;i++) {
        const sushi = eatSushies[i];
        const idDown = idCount*idCount-((idCount-1)*(idCount-1));
        const pointUp = sushies[0].point - sushi.point;
        if(idDown < pointUp)
        {
            eatSushies[i] = sushies[0];
            sushies = sushies[1..$];
            idCount--;
            if(sushies.length==0)
                break;
        }
    }
    writeln(reduce!((a,b)=>a+b.point)(0L, eatSushies) + idCount*idCount);
}
