var lines = []; var result = 0;

var readline = require("readline");

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    var N = Number(lines[0].split(" ")[0])
    var K = Number(lines[0].split(" ")[1])
    lines.shift();

    var td = lines.map(i => i.split(" ").map(i => Number(i)));

    td.sort((a, b) => {
        if (a[0] < b[0]) { return (-1); }
        if (b[0] < a[0]) { return (1); }
        if (a[0] === b[0]) { return (b[1] - a[1]); }
    });

    var sushi = []; var x = {}; var ans = 0;
    for (var i = 0; i < K; i++) {
        var t = td[i][0]; var d = td[i][1];

        if (x[t] === undefined) {
            ans -= Math.pow(Object.keys(x).length, 2); x[t] = 1; ans += Math.pow(Object.keys(x).length, 2);
        }
        else { x[t]++; }

        ans += d;
        sushi.push(td[i]);
    }

    
    for (var i = K; i < N; i++) {
        var t_i = td[i][0]; var d_i = td[i][1];

        for (var j = 0; j < K; j++) {
            var t_j = sushi[j][0]; var d_j = sushi[j][1];
            var ans_before = ans;

            ans -= Math.pow(Object.keys(x).length, 2);
            x[t_j]--; if (x[t_j] === 0) { delete x[t_j] }
            ans -= d_j;

            if (x[t_i] === undefined) { x[t_i] = 1;}
            else { x[t_i]++; }
            ans += Math.pow(Object.keys(x).length, 2);

            ans += d_i;

            if (ans_before < ans) { sushi.splice(j, 1); sushi.push(td[i]); }
            else {
                ans = ans_before;
                if (x[t_j] === undefined) { x[t_j] = 1; } else { x[t_j]++; }
                x[t_i]--; if (x[t_i] === 0) { delete x[t_j] }
            }


        }
    }

    console.log(ans)
});