#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
// #include <boost/foreach.hpp>
// #include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
//#define INF 1e9
#define LINF (1<<40)
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define int long long
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
// int dx[]={0,1,0,-1};
// int dy[]={1,0,-1,0};
typedef pair<int,int> P;

const long long MOD=1000000007LL;
bool isupper(char c){if('A'<=c&&c<='Z')return 1;return 0;}
bool islower(char c){if('a'<=c&&c<='z')return 1;return 0;}
bool iskaibun(string s){for(int i=0;i<s.size()/2;i++)if(s[i]!=s[s.size()-i-1])return 0;return 1;}
bool isnumber(char c){return ('0'<=c&&c<='9');}
bool isalpha(char c){return (isupper(c)||islower(c));}
template<typename T> 
void print(vector<T> v){
    for(int i=0;i<v.size();i++){
        cout<<i<<": ";
        if(i)cout<<" ";
        cout<<v[i];
    }
    cout<<endl;
}
int INF=1e18;

template<typename T>
void printendl(vector<T> v){
    for(auto date:v)cout<<date<<endl;
}

template<typename T>
void printvv(vector<vector<T>> v){
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v[i].size();j++){
            if(j)cout<<" ";
            cout<<v[i][j];
        }
        cout<<endl;
    }
}
int gcd(int a,int b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    else return gcd(b,a%b);
}

struct Edge{
    int to,cost;
};


signed main (){
    int n,k;
    cin>>n>>k;
    vector<vector<int>> v(n);
    rep(i,0,n){
        int t,d;cin>>t>>d;
        t--;
        v[t].push_back(d);
    }
    rep(i,0,n){
        sort(all(v[i]),greater<int>());
        if(v[i].empty())v[i].push_back(-(10000000000000));
    }
    sort(all(v),[&](vector<int> a,vector<int> b){
        return a[0]>b[0];
    });
    //printvv(v);

    int sum=0;
    priority_queue<int> pq;
    rep(i,0,k){
        sum+=v[i][0];
        rep(j,1,v[i].size())pq.push(v[i][j]);
    }
    rep(i,k,n)rep(j,0,v[i].size())pq.push(v[i][j]);

    int ans=sum+k*k;
    for(int x=k-1;x>0;x--){
        int V=v[x][0];
        int W=pq.top();
        if(V<W){
            pq.pop();
            sum+=W;
            pq.push(V);
            sum-=V;
        }
        ans=max(ans,sum+x*x);
    }
    cout<<ans<<endl;

}

/*
#include <iostream>
#include <queue>
#include <algorithm>
#include <numeric>
using namespace std;
const long long INF = 1LL<<40;

int main() {
    long long N, K; cin >> N >> K;
    vector<vector<long long> > s(N); // s[i] := 種類 i の美味しさの集合
    for (int i = 0; i < N; ++i) {
        long long t, d; cin >> t >> d; --t;
        s[t].push_back(d);
    }

    // 各種類について、美味しい順に並べる
    for (auto &v : s) {
        sort(v.begin(), v.end(), greater<long long>());
        if (v.empty()) v.push_back(-INF); // 番兵
    }

    // 「美味しさの最大値」の大きいネタ順
    sort(s.begin(), s.end(), [&](vector<long long> a, vector<long long> b) {
            return a[0] > b[0];});
 
    // まず K 種類選ぶ場合
    long long cur = 0;
    priority_queue<long long> que;
    for (int i = 0; i < K; ++i) {
        cur += s[i][0];
        for (int j = 1; j < s[i].size(); ++j) que.push(s[i][j]);
    }
    for (int i = K; i < N; ++i) for (int j = 0; j < s[i].size(); ++j) que.push(s[i][j]);

    // 走査
    long long res = cur + K*K;
    for (long long x = K-1; x >= 1; --x) {
        long long v = s[x][0];
        long long w = que.top();
        if (v < w) {
            que.pop(); cur += w;
            que.push(v); cur -= v;
        }
        res = max(res, cur + x*x);
    }
    cout << res << endl;
}
*/



Measured memory_bytes: 8696