function f(n) {
    if (n % 2 == 0) {
        return parseInt(n / 2);
    } else {
        return parseInt(3 * n + 1);
    }
}
function Main(input) {
    input = input.split("\n");
    var l0 = input[0].split(" ");
    var N = parseInt(l0[0]);
    var K = parseInt(l0[1]);
    var n, n0, n1, n2;
    var t = [];
    var d = [];
    for (n=1; n<=N; n++) {
        var ln = input[n].split(" ");
        t.push(parseInt(ln[0]));
        d.push(parseInt(ln[1]));
    }
    var max = 0;
    function comb2(n1, n2) {
        var m = new Array(100001);
        var nest = 0;
        var col = 1;
        nest0(nest, col, n1, n2, m);
    }
    function nest0(nest, col, n1, n2, m) {
        var i, k;
        for (i=nest+1; i<=n2+col;i++) {
            m[col]=i;
            if (n1 != col) {
                nest0(i, col+1, n1, n2, m);
            } else {
                var sum = 0;
                var s = new Set();
                for (k=1; k<=n1;k++) {
                    s.add(t[k-1]);
                    sum += d[k-1];
                }
                var mm = s.size * s.size;
                mm += sum;
                max = Math.max(max, mm);
            }
        }
    }

    comb2(K, N-K);

console.log(max);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

