#include <cstdio>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <utility>
#include <vector>
#include <stdio.h>
#include <numeric>
#include <array>

using namespace std;

#define REP(i,from,to) for( long long int i = (from); i < (to); i++ )
#define REV(v) for (auto itr = v.rbegin(); itr != v.rend(); itr++)
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a));
#define MINUS(a) memset(a,-1,sizeof(a));
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pi pair<int, int>
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define VL(v,n) vector<ll> v(n);
#define Read_VL(v,n) vector<ll> v(n);REP(i,0,n)cin>>v[i];
#define sumV(v,n) Vl(acm,n) REP(i,0,n) acm[i] = v[i] + ( i == 0 ? 0 : acm[i - 1]);
#define EPS (1e-10)
#define INF 1000000000000LL

void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}


template <typename ELEMENT_TYPE>
struct _setfillw {
    ELEMENT_TYPE c;
    std::streamsize w;
    _setfillw(ELEMENT_TYPE c, std::streamsize w) : w(w), c(c) {}
};

template <typename ELEMENT_TYPE>
inline _setfillw<ELEMENT_TYPE> setfillw(ELEMENT_TYPE c, std::streamsize w) {
    return _setfillw<ELEMENT_TYPE>(c, w);
}

template <typename ELEMENT_TYPE>
inline std::ostream& operator << (std::ostream& os, const _setfillw<ELEMENT_TYPE>& manip)
{
    return os << std::setw(manip.w) << std::setfill(manip.c);
}

template<class T=ll>struct Graph{
	int n;
	vector<vector<tuple<ll,T>>>edge;
	Graph(int N=1):n(N){edge.resize(n);}
	void add(ll f,ll t,T c,bool d=false){
		edge[f].emplace_back(t,c);
		if(!d)edge[t].emplace_back(f,c);
	}
	void view(){
		REP(i,0,n)for(auto&e:edge[i])
			puta(i,"=>",get<0>(e),", cost :",get<1>(e));
	}
};


bool length_cmp( string &a, string &b ){
  return a.size() < b.size();
}

ll StoLL( string s )
{
	ll num=0;
  REP( i, 0, s.size() ){
    num = num * 10 + ( s[i] ^ 48 );
  }
  return num;
}

ll CtoLL( char c )
{
	if( 'a' <= c && c <= 'z'){
		return (ll)( c ^ 96 ) ;
	}
	else if( 'A' <= c && c <= 'Z'){
		return (ll)( c ^ 64 );
	}
  return 0;
}

ll MOD=1000000007;
ll dx[4] = { 1, 0, -1, 0 };
ll dy[4] = { 0, 1, 0, -1 };

typedef pair<ll, ll> P;

signed main(){
  LIN(n) LIN(k) vector<ll> f( n + 10 );
  priority_queue<P> q;
  priority_queue< P, vector<P>, greater<P> > q2;
  REP( i, 0, n ){
    LIN(t) LIN(d)
    q.push( P( d, t ) );
  }
  ll co = 0;
  ll s = 0, x = 0, ans = 0;
  while( co < k ){
    P p = q.top(); q.pop();
    q2.push( p );
    s += p.first;
    if( f[ p.second ] == 0 ) x++;
    f[ p.second ] ++;
    co++;
  }
  ans = s + x * x;
  while( !q.empty() ){
    P p = q.top();q.pop();
    if( f[ p.second ] ) continue;
    ll m = -1;
    while( !q2.empty() ){
      P p2 = q2.top(); q2.pop();
      if( f[ p2.second ] > 1 ){
        f[ p2.second ]--;
        m = p2.first;
        break;
      }
    }
    if( m == -1 )break;
    x++;
    f[ p.second ]++;
    s += p.first;
    s -= m;
    ans = fmax( ans, s + x * x );
  }
  puta( ans );
  return 0;
}


Measured memory_bytes: 5616