import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N, long K, long[] t, long[] d) {
    alias Sushi = Tuple!(long, "d", long, "t");

    auto s = make!(RedBlackTree!(Sushi, "a > b", true));
    foreach (di, ti; zip(d, t))
        s.insert(Sushi(di, ti));
    
    long[long] hist;
    long dp;
    auto bag = make!(RedBlackTree!(Sushi, "a < b", true));
    foreach (_; 0 .. K) {
        auto x = s.front;
        s.removeFront;

        hist[x.t]++;
        dp += x.d;
        bag.insert(x);
    }
    
    long tp = hist.keys.length;
    long ans = dp + tp ^^ 2;

    while (true) {
        while (!bag.empty && hist[bag.front.t] <= 1)
            bag.removeFront;
        if (bag.empty) break;
        
        dp -= bag.front.d;
        hist[bag.front.t]--;
        bag.removeFront;
        
        while (!s.empty && s.front.t in hist)
            s.removeFront;
        if (s.empty) break;

        dp += s.front.d;
        hist[s.front.t]++;
        tp++;
        s.removeFront;

        ans = max(ans, dp + tp ^^ 2);
    }

    return ans;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long K;
    K = input.front.to!long;
    input.popFront;

    long[] t = new long[](cast(size_t) (N));
    long[] d = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        t[i] = input.front.to!long;
        input.popFront;
        d[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, K, t, d);
    else
        solve(N, K, t, d).writeln;
}
