// Header
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <cmath>
    #include <list>
    #include <iomanip>
    #include <stack>
    #include <queue>
    using namespace std;
//

// Constants
    using lint = long long;
    const lint MOD = 1e9 + 7;
    const int INF = 1e9;
    const lint LINF = 1e18;
    using flt = double;
    const flt E = exp(1.0);
    const flt PI = acos(-1.0);
//

// Class ModInteger<MOD>
/*
    template <lint mod>
    class ModInteger {
        public:
        lint val;

        // Constructor
        ModInteger(): val(0) {}
        ModInteger(lint ival): val(ival >= 0? ival%mod: mod - (-ival)%mod) {}

        // Comparators
        bool operator !() {return val == 0;}
        bool operator <(ModInteger that) {return val < that.val;}
        bool operator >(ModInteger that) {return val > that.val;}
        bool operator <=(ModInteger that) {return val <= that.val;}
        bool operator >=(ModInteger that) {return val >= that.val;}
        bool operator ==(ModInteger that) {return val == that.val;}
        bool operator !=(ModInteger that) {return val != that.val;}

        // Basic operations
        ModInteger operator ++() {val++; return *this;}
        ModInteger operator --() {val--; return *this;}

        ModInteger& operator +=(ModInteger that) {val = (val + that.val)%mod; return *this;}
        ModInteger& operator -=(ModInteger that) {val = ((val - that.val)%mod + mod)%mod; return *this;}
        ModInteger& operator *=(ModInteger that) {val = (val*that.val)%mod; return *this;}
        ModInteger& operator /=(ModInteger that) {
            lint inv = that.val, rem = 1, power = mod - 2;
            while (power > 1) {if (power%2) rem = (rem*inv)%mod; inv = (inv*inv)%mod; power /= 2;}
            inv = (rem*inv)%mod;
            val = (val*inv)%mod;
            return *this;
        }

        ModInteger operator +(ModInteger that) {return ModInteger(*this) += that;}
        ModInteger operator -(ModInteger that) {return ModInteger(*this) -= that;}
        ModInteger operator *(ModInteger that) {return ModInteger(*this) *= that;}
        ModInteger operator /(ModInteger that) {return ModInteger(*this) /= that;}
        
        ModInteger& operator %=(ModInteger that) {val = val%that.val; return *this;}
        ModInteger operator %(ModInteger that) {return ModInteger(*this) %= that;}
    }; using mint = ModInteger<MOD>;

    // ModInteger input & output
    istream& operator >>(istream& is, mint& n) {return is >> n.val;}
    ostream& operator <<(ostream& os, mint n) {return os << n.val;}
*/
//

// Macros
    #define rep(i, n) for (int i = 0; i < n; i++)
    #define rep1(i, n) for (int i = 1; i <= n; i++)
    #define bit(n) (lint)1<<n
    #define mrep(it, m) for (auto it = m.begin(); it != num.end(); it++)
    #define fi first
    #define se second
    #define pint pair<int, int>
    #define plint pair<lint, lint>
    #define mp make_pair
    #define vint vector<int>
    #define vvint vector<vector<int>>
    #define vlint vector<lint>
    #define vvlint vector<vector<lint>>
    #define pb push_back
    #define all(v) v.begin(), v.end()
    #define asort(v) sort(all(v))
    #define dsort(v) sort(all(v)); reverse(all(v))
    #define maxval(v) *max_element(all(v))
    #define maxindex(v) distance(v.begin(), max_element(all(v)))
    #define minval(v) *min_element(all(v))
    #define minindex(v) distance(v.begin(), min_element(all(v)))
//

// Basic functions (be careful of overflowing!)
    template <typename Tp>
    Tp gcd(Tp m, Tp n) {
        if (!m || !n) {cout << "GCD error: zero inputed" << endl; return 0;}
        else if (!(m%n)) return n;
        else return gcd(n, m%n);
    }
    template <typename Tp>
    Tp lcm(Tp m, Tp n) {
        if (!m || !n) {cout << "LCM error: zero inputed" << endl; return 0;}
        else return m*n/gcd(m, n);
    }
    template <typename Tp>
    Tp ipow(Tp a, Tp p) {// For integers
        if (p < 0) {cout << "Power error: a minus number inputed" << endl; return 0;}
        else if (!p) return 1;
        Tp res = a, rem = 1;
        while (p > 1) {if (p%2) rem *= res; res *= res; p /= 2;}
        return rem*res;
    }
    template <typename Tp>
    Tp fact(Tp n) {// Facorial: requires O(n)
        if (n < 0) {cout << "Factorial error: a minus number inputed" << endl; return 0;}
        else if (!n) return 1;
        else if (n == 1) return 1;
        else return n*fact(n - 1);
    }
    template <typename Tp>
    void pfact(Tp n, map<Tp, int>& res) {// Prime factorization: requires O(sqrt(n))
        if (n <= 1) {cout << "Prime factorization error: cannot factorize an integer less than 2" << endl; return;}
        if (res.size()) cout << "Prime factorization warning: the map already contains some numbers" << endl;
        Tp pos = 2, pmax = n;
        while (pos*pos <= pmax) {if (!(n%pos)) {res[pos]++; n /= pos;} else pos++;}
        if (n != 1) res[n]++;
        return;
    }
    template <typename Tp>
    Tp comb(Tp n, Tp r) {// Requires O(r)
        if (n < 0 || r < 0) {cout << "Combination error: a minus number inputed" << endl; return 0;}
        else {lint res = 1; rep(i, r) res *= (n - i)/(i + 1); return res;}
    }
//

// Basic solutions for graph problems
/*
    template <typename Tp>
    void warshall_floyd(vector<vector<Tp>>& dist) {
        int n = dist[0].size();
        rep(k, n) rep(i, n) rep(j, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        return;
    }
*/
//

// Format for cout (example)
/*
    // Integers
    cout << 42; -> 42
    cout << setfill('0') << setw(6) << 42; -> 000042

    // Floats
    cout << PI; -> 3.14159
    cout << fixed << PI; -> 3.141593 
    cout << fixed << setprecision(8) << PI; -> 3.14159265
*/

struct Sushi {
    lint t, d;
    bool operator <(Sushi that) {return d != that.d? d < that.d: t < that.t;}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, K; cin >> N >> K;
    vector<Sushi> s(N); rep(i, N) cin >> s[i].t >> s[i].d;

    dsort(s);

    lint sum = 0; map<lint, int> num;
    rep(i, K) {sum += s[i].d; num[s[i].t]++;}

    lint kind = num.size(), ans = sum + kind*kind;
    int pos = K;
    for (int i = K - 1; i >= 0; i--) {
        if (num[s[i].t] > 1) {
            num[s[i].t]--; sum -= s[i].d;
            while (pos < N && num[s[pos].t]) pos++;
            if (pos == N) break;
            num[s[pos].t]++; sum += s[pos].d; kind++;
            ans = max(ans, sum + kind*kind);
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5888