// Original C++ solution (slower):
#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();

        }

        

        if(clr[s[i].sc]==0) {

            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]++; kind++;

            chmax(ans, t+kind*kind);

        }

        

    }



    pt(ans);

}






// Optimized solution to the same problem (faster):
#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);

}






// Fastest known solution for this problem: