stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

using namespace std;



int main()

{

    ////////////////////////////

    //入力

    int n,k;

    cin >> n >> k;



    int a[n];

    for (int i=0; i<n; i++){

	cin >> a[i];

    }



    //計算

    int cnt[200000]={};

    int types = 0;



    for (int i=0; i<n; i++){

	//もしi番目のボールの数字が初登場なら種類数を1増やす

	if (cnt[a[i]] == 0){

	    types++;

	}

	//「i番目のボールに書かれていた数字」の登場回数メモを1増やす

	cnt[a[i]]++;

    }

    

    //既にk種類以下の場合、書き換える数は0なので出力して終了する

    if (types <= k){

	cout << 0 << endl;

	return 0;

    }

    int ans = 0;

    for (int f=1; f<200000; f++){

        for (int j=0; j<200000; j++){

	    //登場回数が1回の数字から書き換えて行く

	    if (cnt[j] == f){

	        types--;

		ans += f;

		if (types <= k){

		    cout << ans << endl;

		    return 0;

		}

	    }

	}

    }

    ////////////////////////////

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8042000693944897x):
#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

    ////////////////////////////

    //入力

    int n,k;

    cin >> n >> k;



    int a;

    int cnt[n+1] = {};

    for (int i=0; i<n; i++){

	cin >> a;

	cnt[a]++;

    }



    //計算

    sort(cnt, cnt+n+1);

    int types = 0;



    for (int i=0; i<n+1; i++){

	if (cnt[i] > 0){

	    types++;

	}

    }

    

    int num = max(0, types-k);

    int ans = 0;

    int i = 0;

    while( cnt[i] == 0 ){

	i++;

    }

    for (int j=0; j<num; j++){

	ans += cnt[i];

	i++;

    }

    cout << ans << endl;

    ////////////////////////////

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long int llint;



int main(){

	int n, k, i, ans=0;

	int a[200010];

	int num[200010]={};

	cin>>n>>k;

	for(i=0; i<n; i++) cin>>a[i];

	for(i=0; i<n; i++) num[a[i]]++;

	sort(num+1, num+n+1);

	if(k==n){

		cout<<0<<endl;

		return 0;

	}

	for(i=1; i<=n-k; i++) ans+=num[i];

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7617993738353797x):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



#define REP(i, n) for(int i=0; i<(n); ++i)

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)



#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'

#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'

#define ALL(a) (a).begin(), (a).end()



template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}

template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}



constexpr ll MOD=1000000007ll;

// constexpr ll MOD=998244353ll;

#define FIX(a) ((a)%MOD+MOD)%MOD



const double EPS=1e-11;

#define EQ0(x) (abs((x))<EPS)

#define EQ(a, b) (abs((a)-(b))<EPS)



int num[252521];



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	// cout<<setprecision(10)<<fixed;

	int n, k, a[252521];

	cin>>n>>k;

	REP(i, n){

		cin>>a[i];

		++num[a[i]];

	}

	sort(num, num+n+1);

	int ans=0, cnt=0;

	FORR(i, 0, n+1){

		++cnt;

		if(cnt>k){

			ans+=num[i];

		}

	}

	cout<<ans<<'\n';

	return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"



typedef long long ll;



const int MAX_SIZE = 2e5 + 5;



int freq[MAX_SIZE];



int main()

{

	int n, k;

	scanf("%d%d", &n, &k);

	for (int i = 0; i < n; ++i)

	{

		int temp;

		scanf("%d", &temp);

		++freq[temp];

	}

	std::vector<int> v;

	v.reserve(MAX_SIZE);

	for (int i = 0; i < MAX_SIZE; ++i)

	{

		if (freq[i])

		{

			v.push_back(freq[i]);

		}

	}

	std::sort(v.begin(), v.end());

	ll ans = 0;

	int end = v.size() - k;

	for (int i = 0; i < end; ++i)

	{

		ans += v[i];

	}

	printf("%lld\n", ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7576811645374502x):
#include <bits/stdc++.h>

#include<iostream>

#define point complex<double>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const int N=2e5+10,mod=1e9+7;

ll inf=LONG_LONG_MAX;

int a[N];

int GCD(int a, int b) {

	if(b==0)

    	return a;

	else

    	return GCD(b, a%b);

}







int main()

{

  /* ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);*/

   ll n,k;



   cin>>n>>k;

   map<ll,ll>mp;

   for(int i=0;i<n;i++){

       int x;

   cin>>x;

       mp[x]++;



   }

   vector<ll>val;

   map<ll,ll>::iterator it=mp.begin();

    for(it;it!=mp.end();it++){

            val.push_back(it->second);



       }

       sort(val.begin(),val.end());

   if(val.size()>k){

        ll ans=0;







        for(int i=0;i<val.size()-k;i++){



      ans+=val[i];





       }

    cout<<ans;

    return 0;



   }

   cout<<0;





    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>



using namespace std;



int main(void)

{

  int ki[200000]={0};

  int N,K,cnt=0;

  int max=-1;

  

  cin >> N >> K;

  int A[N];

  for(int i=0;i<N;i++){

    cin >> A[i];

    ki[A[i]]++;

    if(max<A[i])

      max=A[i];

  }

  

  sort(ki,ki+max+1);

  for(int i=0;i<max-K+1;i++)

    cnt+=ki[i];



  cout << cnt << endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7938866622487422x):
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int main()

{

  int N, K;

  cin >> N >> K;

  vector<int> hist(N + 1, 0);

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }



  sort(hist.begin(), hist.end());

  int idx = 0;

  while (hist[idx] == 0) idx++;

  int ans = 0;

  for (int i = idx; N - i + 1 > K; i++) {

    ans += hist[i];

  }

  cout << ans << endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int hist[210000];



int main()

{

  int N, K;

  cin >> N >> K;

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }

  

  vector<int> v;

  for (int i = 1; i <= 200000; i++) {

	if (hist[i] > 0) v.push_back(hist[i]);

  }

  sort(v.begin(), v.end());

  

  int ans = 0;

  for (int i = 0; i < (int)v.size() - K; i++) {

  	ans += v[i];

  }

  cout << ans << endl;

  

  return 0;

}

  

// Faster C++ solution for the same problem (measured speedup: 1.775790972215497x):
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int main()

{

  int N, K;

  cin >> N >> K;

  vector<int> hist(N + 1, 0);

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }



  sort(hist.begin(), hist.end());

  int idx = 0;

  while (hist[idx] == 0) idx++;

  int ans = 0;

  for (int i = idx; N - i + 1 > K; i++) {

    ans += hist[i];

  }

  cout << ans << endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>



using namespace std;



int main(void)

{

  int ki[200000]={0};

  int N,K,cnt=0;

  int max=-1;

  

  cin >> N >> K;

  int A[N];

  for(int i=0;i<N;i++){

    cin >> A[i];

    ki[A[i]]++;

    if(max<A[i])

      max=A[i];

  }

  

  sort(ki,ki+max+1);

  for(int i=0;i<max-K+1;i++)

    cnt+=ki[i];



  cout << cnt << endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7939923937117512x):
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int main()

{

  int N, K;

  cin >> N >> K;

  vector<int> hist(N + 1, 0);

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }



  sort(hist.begin(), hist.end(), greater<int>());

  int tmp = 0;

  for (int i = 0; i < K; i++) {

    tmp += hist[i];

  }

  cout << (N - tmp) << endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int hist[210000];



int main()

{

  int N, K;

  cin >> N >> K;

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }

  

  vector<int> v;

  for (int i = 1; i <= 200000; i++) {

	if (hist[i] > 0) v.push_back(hist[i]);

  }

  sort(v.begin(), v.end());

  

  int ans = 0;

  for (int i = 0; i < (int)v.size() - K; i++) {

  	ans += v[i];

  }

  cout << ans << endl;

  

  return 0;

}

  

// Faster C++ solution for the same problem (measured speedup: 1.7758956371207233x):
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int main()

{

  int N, K;

  cin >> N >> K;

  vector<int> hist(N + 1, 0);

  for (int i = 0; i < N; i++) {

    int A;

    cin >> A;

    hist[A]++;

  }



  sort(hist.begin(), hist.end(), greater<int>());

  int tmp = 0;

  for (int i = 0; i < K; i++) {

    tmp += hist[i];

  }

  cout << (N - tmp) << endl;



  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<vector>

using namespace std;

#define N 50000

bool prime[N];

vector<int> primes;



void init(){

	primes.clear();

	memset(prime,true,sizeof(prime));

	prime[0] = prime[1] = true;

	for(int x=2;x<N;++x){

		if(prime[x]){

			primes.push_back(x);

			for(int i=x+x;i<N;i+=x){

				prime[i] = false;

			}

		}

	}

}



int main(){

	init();

	int c;

	while(cin>>c,c){

		int cnt = 0;

		for(int x=0;x<primes.size();++x){

			for(int y=x;y<primes.size();++y){

				if(primes[x]+primes[y]==c)cnt++;

				if(primes[x]+primes[y] > c)break;

			}

			if(primes[x] >= c ) break;

		}

		cout<<cnt<<endl;	

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2577978741665785x):
#include<iostream>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<vector>

using namespace std;

#define N 33000

bool prime[N];

//vector<int> primes;



void init(){

	//primes.clear();

	memset(prime,true,sizeof(prime));

	prime[0] = prime[1] = false;

	for(int x=2;x<N;++x){

		if(prime[x]){

			//primes.push_back(x);

			for(int i=x+x;i<N;i+=x){

				prime[i] = false;

			}

		}

	}

}



int main(){

	init();

	int c;

	while(cin>>c,c){

		int cnt = 0;

		for(int x=0;x<c/2+1;++x){

			if(prime[x] && prime[c-x]){

				cnt++;

				//cout<<x<<":"<<c-x<<endl;

			}

		}

		cout<<cnt<<endl;	

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef pair<int,int> P;



int main(void){

    int n,k;

    long long s=0,t,u[100002],w;

    vector<int> v[100002];

    priority_queue<P, vector<P>, greater<P>> q;

    P p[100002];

    map<int,int> m;

    cin>>n>>k;

    for(int i=0;i<n;i++){

        int t,d;

        cin>>t>>d;

        p[i].first=d;

        p[i].second=t;

    }

    sort(p,p+n,greater<P>());

    for(int i=0;i<k;i++){

        s+=p[i].first;

        m[p[i].second]++;

        u[p[i].second]+=p[i].first;

        q.push(p[i]);

    }

    //cout<<m[3]<<endl;

    w=m.size();

    t=s+w*w;

    for(int i=k;i<n;i++){

        if(m[p[i].second]==0){

            bool wh=true;

            while(!q.empty()&&wh){

                P z=q.top();

                q.pop();

                if(m[z.second]>1){

                    s-=z.first;

                    s+=p[i].first;

                    m[p[i].second]++;

                    w++;

                    t=max(t,s+w*w);

                    wh=false;

                }

            }

            if(wh)break;

        }

        //cout<<p[i].first<<p[i].second<<endl;

        //cout<<"---"<<m[p[i].second]<<endl;

        //cout<<"i"<<i<<" "<<s<<endl;

    }

    cout<<t<<endl;

    

}


// Faster C++ solution for the same problem (measured speedup: 1.6781640467449321x):
#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

using namespace std;

typedef long long ll;

typedef pair<ll, int> P;

int main(void){

    int n, k;

    ll m=0, x=0;

    P p[100000];

    set<int> s;

    priority_queue<int, vector<int>, greater<int> > q;

    

    cin>>n>>k;

    for(int i=0;i<n;i++){

        int t, d;

        cin>>t>>d;

        p[i]=P(d, t);

    }

    sort(p, p+n, greater<P>());

    for(int i=0;i<n;i++){

        int d=p[i].first, t=p[i].second;

        if(i<k){

            if(s.find(t)==s.end()){

                s.insert(t);

            }else{

                q.push(d);

            }

            x+=d;

        }else if(s.find(t)==s.end()&&!q.empty()){

            s.insert(t);

            int w=q.top();

            q.pop();

            x+=d-w;

        }

        if(i>=k-1){

            ll w=s.size();

            m=max(m, x+w*w);

        }

    }

    cout<<m<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef pair<int,int> P;



int main(void){

    int n,k;

    long long s=0,t,u[100002],w;

    vector<int> v[100002];

    priority_queue<P, vector<P>, greater<P>> q;

    P p[100002];

    map<int,int> m;

    cin>>n>>k;

    for(int i=0;i<n;i++){

        int t,d;

        cin>>t>>d;

        p[i].first=d;

        p[i].second=t;

    }

    sort(p,p+n,greater<P>());

    for(int i=0;i<k;i++){

        s+=p[i].first;

        m[p[i].second]++;

        u[p[i].second]+=p[i].first;

        q.push(p[i]);

    }

    //cout<<m[3]<<endl;

    w=m.size();

    t=s+w*w;

    for(int i=k;i<n;i++){

        if(m[p[i].second]==0){

            bool wh=true;

            while(!q.empty()&&wh){

                P z=q.top();

                q.pop();

                if(m[z.second]>1){

                    s-=z.first;

                    s+=p[i].first;

                    m[p[i].second]++;

                    w++;

                    t=max(t,s+w*w);

                    wh=false;

                }

            }

            if(wh)break;

        }

        //cout<<p[i].first<<p[i].second<<endl;

        //cout<<"---"<<m[p[i].second]<<endl;

        //cout<<"i"<<i<<" "<<s<<endl;

    }

    cout<<t<<endl;

    

}


// Faster C++ solution for the same problem (measured speedup: 4.3730544915629705x):
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;



struct S{

    int t, d;

    S(int t, int d) : t(t), d(d){}

    bool operator<(const S& s) const {

        if(d != s.d) return d > s.d;

        return t < s.t;

    }

};



int main() {

    int n, k;

    vector<S> ssh;

    long long ans = 0;

    cin >> n >> k;

    ssh.reserve(n);

    for(int i=0;i<n;i++){

        int t, d;

        cin >> t >> d;

        ssh.push_back(S(--t, d));

    }

    sort(ssh.begin(), ssh.end());

    long long sum = 0, srt = 0;

    vector<bool> usd(n, false);

    priority_queue<int, vector<int>, greater<int> > q;

    for(int i=0;i<k;i++){

        int t = ssh[i].t;

        int d = ssh[i].d;

        sum += d;

        if(usd[t]){

            q.push(d);

        }else{

            usd[t] = true;

            srt++;

        }

    }

    ans = sum + srt * srt;

    for(int i=k;i<n;i++){

        if(q.empty()) break;

        int t = ssh[i].t;

        int d = ssh[i].d;

        if(usd[t]) continue;

        int out = q.top(); q.pop();

        sum += d - out;

        usd[t] = true;

        srt++;

        long long tmp = sum + srt*srt;

        if(ans < tmp) ans = tmp;

    }

    cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

using namespace std;

typedef long long ll;

typedef pair<ll, int> P;

int main(void){

    int n, k;

    ll m=0, x=0;

    P p[100000];

    set<int> s;

    priority_queue<int, vector<int>, greater<int> > q;

    

    cin>>n>>k;

    for(int i=0;i<n;i++){

        int t, d;

        cin>>t>>d;

        p[i]=P(d, t);

    }

    sort(p, p+n, greater<P>());

    for(int i=0;i<n;i++){

        int d=p[i].first, t=p[i].second;

        if(i<k){

            if(s.find(t)==s.end()){

                s.insert(t);

            }else{

                q.push(d);

            }

            x+=d;

        }else if(s.find(t)==s.end()&&!q.empty()){

            s.insert(t);

            int w=q.top();

            q.pop();

            x+=d-w;

        }

        if(i>=k-1){

            ll w=s.size();

            m=max(m, x+w*w);

        }

    }

    cout<<m<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.6058563821845726x):
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;



struct S{

    int t, d;

    S(int t, int d) : t(t), d(d){}

    bool operator<(const S& s) const {

        if(d != s.d) return d > s.d;

        return t < s.t;

    }

};



int main() {

    int n, k;

    vector<S> ssh;

    long long ans = 0;

    cin >> n >> k;

    ssh.reserve(n);

    for(int i=0;i<n;i++){

        int t, d;

        cin >> t >> d;

        ssh.push_back(S(--t, d));

    }

    sort(ssh.begin(), ssh.end());

    long long sum = 0, srt = 0;

    vector<bool> usd(n, false);

    priority_queue<int, vector<int>, greater<int> > q;

    for(int i=0;i<k;i++){

        int t = ssh[i].t;

        int d = ssh[i].d;

        sum += d;

        if(usd[t]){

            q.push(d);

        }else{

            usd[t] = true;

            srt++;

        }

    }

    ans = sum + srt * srt;

    for(int i=k;i<n;i++){

        if(q.empty()) break;

        int t = ssh[i].t;

        int d = ssh[i].d;

        if(usd[t]) continue;

        int out = q.top(); q.pop();

        sum += d - out;

        usd[t] = true;

        srt++;

        long long tmp = sum + srt*srt;

        if(ans < tmp) ans = tmp;

    }

    cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))

#define REP(i, n) FOR(i,n,0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll) 1e15;



pll A[100005];

ll U[100005];



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll K, N;

    cin >> N >> K;

    REP(i, N) {

        cin >> A[i].first >> A[i].second;

    }



    sort(A, A + N, [](pll a, pll b) { return a.second > b.second; });

    memset(U, 0, sizeof(U));

    ll ans = 0;



    priority_queue<pll, vector<pll>, function<bool(pll, pll)>> q([](pll a, pll b) { return a.second > b.second; });

    ll k = 0;

    ll x = 0;



    ll sum = 0;

    REP(i, N) {

        k++;

        if (k <= K) {

            sum += A[i].second;

            U[A[i].first]++;

            if (U[A[i].first] > 1) {

                q.push(A[i]);

            }

            else {

                x++;

            }

            ans = std::max(ans, sum + x * x);

            continue;

        }



        if (U[A[i].first] > 0)

            continue;



        if (!q.empty()) {

            pll t = q.top();

            q.pop();

            sum = sum - t.second + A[i].second;

            U[A[i].first]++;

            x++;

            ans = std::max(ans, sum + x * x);

        }

    }



    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.77680922018436x):
#include <bits/stdc++.h>



using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))

#define REP(i, n) FOR(i,n,0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll) 1e15;



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N, K;

    cin >> N >> K;

    priority_queue<pll, vector<pll>, function<bool(pll, pll)>> q([](pll a, pll b) { return a.second < b.second; });

    REP(i, N) {

        pll a;

        cin >> a.first >> a.second;

        q.push(a);

    }



    ll sum = 0;

    ll type = 0;

    map<ll, ll> m;

    priority_queue<ll, vector<ll>, greater<>> q0;

    REP(i, K) {

        pll t = q.top();

        q.pop();

        sum += t.second;

        if (m[t.first]++ == 0)

            type++;

        else

            q0.push(t.second);

    }



    vector<pll> v;

    while (!q.empty() && !q0.empty()) {

        pll t0 = q.top();

        q.pop();

        if (m[t0.first]++ > 0)

            continue;

        ll t1 = q0.top();

        q0.pop();

        pll p(0, 0);

        if (v.size() > 0)

            p = v.back();

        p.first += t0.second;

        p.second += t1;

        v.push_back(p);

    }



    ll ans = sum + type * type;

    REP(i, v.size()) {

        ans = std::max(ans, sum - v[i].second + v[i].first + (type + 1 + i) * (type + 1 + i));

    }



    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp(a, b) make_pair(a, b)

#define pb(t) push_back(t)

#define ft first

#define sc second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N, K;

    cin >> N >> K;

    ll i;

    P s[MAX];

    ll clr[MAX]={};

    

    for(i=0; i<N; i++) cin >> s[i].sc >> s[i].ft;

    sort(s, s+N);

    reverse(s, s+N);

    

    priority_queue<P> q;

    ll ans=0;

    ll t=0;

    ll kind=0;

    

    for(i=0; i<K; i++) {

        q.push(P(-s[i].ft, s[i].sc));

        t+=s[i].ft;

        clr[s[i].sc]++;

        if(clr[s[i].sc]==1) kind++;

    }

    chmax(ans, t+kind*kind);



    for(i=K; i<N; i++) {

        P u=q.top();

        

        while(q.size() && clr[u.sc]==1) {

            q.pop();

            

            if(q.empty()) {

                pt(ans);

                return 0;

            }

            

            u=q.top();

        }

        

        q.pop();

        clr[u.sc]--;

        q.push(P(-s[i].ft, s[i].sc));

        t+=u.ft; t+=s[i].ft;

        

        clr[s[i].sc]++;

        if(clr[s[i].sc]==1) kind++;

        

        chmax(ans, t+kind*kind);

    }



    pt(ans);

}






// Faster C++ solution for the same problem (measured speedup: 1.9111994151238656x):
#include <bits/stdc++.h>

#define ft first

#define sc second

#define lb lower_bound

#define ub upper_bound

#define pb push_back

#define pt(sth) cout << sth << "\n"

#define chmax(a, b) {if(a<b) a=b;}

#define chmin(a, b) {if(a>b) a=b;}

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const ll INF=1e18;

static const ll MAX=1e5+7;

static const ll MOD=1e9+7;

ll max(ll a, ll b) {return a>b?a:b;}

ll min(ll a, ll b) {return a<b?a:b;}







int main(void) {

  ll N, K;

  cin >> N >> K;

  ll i;

  vector<P> su(N);

  ll ty=0;

  ll cnt[MAX]={};

  

  for(i=0; i<N; i++) {

    cin >> su[i].sc >> su[i].ft;

    su[i].sc--;

  }

  sort(su.rbegin(), su.rend());

  

  ll ans=0;

  ll t=0;

  priority_queue<P> q;

  for(i=0; i<K; i++) {

    q.push({-su[i].ft, su[i].sc});

    t+=su[i].ft;

    cnt[su[i].sc]++;

    if(cnt[su[i].sc]==1) ty++;

  }

  ans=t;

  ans+=ty*ty;

  

  for(i=K; i<N; i++) {

    while(q.size()) {

      P f=q.top(); q.pop();

      if(cnt[f.sc]>1) {

        t-=-f.ft;

        cnt[f.sc]--;

        q.push({-su[i].ft, su[i].sc});

        t+=su[i].ft;

        cnt[su[i].sc]++;

        if(cnt[su[i].sc]==1) ty++;

        chmax(ans, t+ty*ty);

        break;

      }

    }

  }

  

  pt(ans);

}