#include <bits/stdc++.h>
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) (UB(c,x)-LB(c,x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define NL cerr << endl;
#define chmax(a, b) a=(((a)<(b))?(b):(a))
#define chmin(a, b) a=(((a)>(b))?(b):(a))
#define F first
#define S second
using namespace std;
template<typename T1, typename T2> using P = pair<T1,T2>;
template<typename T> using V = vector<T>;
struct edge { int from, to; int cost; };
bool operator< (const edge &edge1, const edge &edge2) { return edge1.cost < edge2.cost; };
const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const V<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const P<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}
template<typename T> ostream& operator << (ostream& s, const set<T>& st) {
   s << "{";
   for (auto i = st.begin(); i != st.end(); ++i) {
      s << *i;
      if (next(i) != st.end()) s << ", ";
   }
   s << "}";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const map<T1,T2>& m) {
   s << "{";
   for (auto i = m.begin(); i != m.end(); ++i) {
      s << i->first << ":" << i->second;
      if (next(i) != m.end()) s << ", ";
   }
   s << "}";
   return s;
}

signed main()
{
   int N, K; cin >> N >> K;
   V<int> t(N), d(N);
   REP(i, N) {
      cin >> t[i] >> d[i];
   }


   V<P<int,int>> p(N);
   REP(i, N) {
      p[i] = MP(d[i], t[i]);
   }
   RSORT(p);

   // eat delicious sushi first
   map<int,V<int>> sushi1, sushi2;
   // sushi1: sushi to be eaten first
   // sushi2: sushi not to be eaten first
   int sum = 0;
   FOR(i, 0, K) {
      int t_ = p[i].S, d_ = p[i].F;
      sushi1[t_].PB(d_);
      sum += d_;
   }
   int sz = sushi1.size();
   FOR(i, K, N) {
      int t_ = p[i].S, d_ = p[i].F;
      sushi2[t_].PB(d_);
   }

   V<int> sushi3;
   // sushi3: sushi whose type is already eaten
   EACH(i, sushi1) {
      RSORT(i->S);
      EACH(j, i->S) {
         if (j == i->S.begin()) continue;
         sushi3.PB(*j);
      }
   }
   V<int> sushi4;
   // sushi4: sushi whose type is not eaten yet
   EACH(i, sushi2) {
      if (sushi1[i->F].size() != 0) continue;
      RSORT(i->S);
      sushi4.PB(i->S[0]);
   }

   SORT(sushi3);
   RSORT(sushi4);

   DUMP(sushi3)
   DUMP(sushi4)

   int ans = sum + sz * sz;
   REP(i, min(sushi3.size(), sushi4.size())) {
      sum = sum - sushi3[i] + sushi4[i];
      sz++;
      chmax(ans, sum + sz * sz);
   }
   cout << ans << endl;

   return 0;
}


Measured memory_bytes: 18552