#include <bits/stdc++.h>

#define ioFix ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

long long madd(long long x, long long y, long long modulo) {
  return (x + y) % modulo;
}

long long mmult(long long x, long long y, long long modulo) {
  return (x * y) % modulo;
}

long long mpow(long long base, long long exponent, long long modulo) {
  long long res = 1;
  for(int i = 0; i < exponent; i++)
    res = (res * base) % modulo;
  return res;
}

long long mfac(long long n, long long modulo) {
  long long res = 1;
  for(int i = 2; i <= n; i++)
    res = (res * i) % modulo;
  return res;
}

// Slower, DP approach
long long mcombDP(long long n, long long k, long long modulo) {
  long long C[k+1];
  memset(C, 0, sizeof(C));
  C[0] = 1;

  for(long long i = 1; i <= n; i++)
    for(long long j = std::min(i, k); j > 0; j--)
      C[j] = (C[j] + C[j - 1]) % modulo;
  return C[k];
}

// Lucas theorem
long long mcomb(long long n, long long k, long long modulo) {
  if(k == 0)
    return 1;

  return (
          mcomb(n / modulo, k / modulo, modulo) *
          mcombDP(n % modulo, k % modulo, modulo)
          ) % modulo;
}


#define PI (2.0 * acos(0.0))
#define INF (int)1e9
#define LINF (long long)1e18
#define EPS 1e-9

#define ll long long
#define ull unsigned long long

#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define pcc pair<char, char>
#define pbb pair<bool, bool>

#define tiii tuple<int, int, int>

#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vld vector<long double>
#define vvld vector<vector<long double>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vvs vector<vector<string>>

#define REP(n) for(int xix = 0; xix < (n); xix++)
#define FOR(i, from, to) for(int (i) = from; (i) < (to); (i)++)
#define RFOR(i, from, to) for(int (i) = to-1; (i) >= (from); (i)--)
#define RANGE(i, from, to) for(int (i) = from; (i) <= (to); (i)++)
#define RRANGE(i, from, to) for(int (i) = to; (i) >= (from); (i)--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()

#define pb push_back
#define mp make_pair
#define mt make_tuple

#define fillArray(arr, val) std::fill(std::begin(arr), std::end(arr), (val))

#define pow2(x) ((x)*(x))
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))

#define watch(x) cout << (#x) << " is " << (x) << endl
#define watchVector(v) { for(int xvx = 0; xvx < (v).size(); xvx++) { cout << (v)[xvx] << " "; } cout << endl; }
#define watchArray(arr, n) { for(int xax = 0; xax < (n); xax++) { cout << (arr)[xax] << " "; } cout << endl; }
#define watchMatrix(x, rows, cols) for(int r = 0; r < (rows); r++) { for(int c = 0; c < (cols); c++) { cout << (x)[r][c] << " "; } cout << endl; }

/* Requires GNU C++ */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace __gnu_pbds;

/*
  typedef base_name<
    key,
    mapped,
    key_comp_func,
    tag_specifying_datastructure,
    updating_node_invariants_policy> my_name;


  my_name s;
  s.insert(x);
  s.find_by_order(i); // index->value
  s.order_of_key(x); // value->index
 */

namespace std {
  typedef trie<
    std::string,
    null_type,
    trie_string_access_traits<>,
    pat_trie_tag,
    trie_prefix_search_node_update> pref_trie;

  typedef tree<
    int,
    null_type,
    std::less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> order_set;
}



using namespace std;


int main() {
  ioFix;
  int K, N;
  cin >> N >> K;
  vector<pii> sushi(N); // <delicious, type>
  FOR(i, 0, N)
    cin >> sushi[i].second >> sushi[i].first;

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

  ll x = 0;
  ll sum = 0;
  map<int, int> hasType; // <type, counter>
  FOR(i, 0, K) {
    if(hasType[sushi[i].second] == 0) x++;
    hasType[sushi[i].second]++;
    sum += sushi[i].first;
  }

  int roof = K-x;
  vi potIndices;

  int low = K-1;
  while(potIndices.size() < roof) {
    while(low >= 0 && hasType[sushi[low].second] == 1)
      low--;
    potIndices.pb(low);
    low--;
  }

  vll potX(roof+1);
  vll potSum(roof+1);
  potX[0] = x;
  potSum[0] = sum;

  // FOR(i, 0, roof)
  //   cout << potIndices[i] << " ";
  // cout << endl;

  int p = 1;
  low = 0;
  FOR(i, K, N) {
    if(p > roof)
      break;
    if(hasType[sushi[i].second] > 0)
      continue;

    // cout << potSum[p-1] << endl;
    // cout << sushi[potIndices[low]].first << endl;
    // cout << sushi[i].first << endl;
    // cout << endl;
    potSum[p] = potSum[p-1] - sushi[potIndices[low]].first + sushi[i].first;
    potX[p] = potX[p-1]+1;

    hasType[sushi[potIndices[low]].second]--;
    hasType[sushi[i].second]++;

    low++;
    p++;
  }

  ll res = 0;
  FOR(i, 0, roof+1) {
    //cout << potSum[i] + potX[i] * potX[i] << endl;
    res = max(res, potSum[i] + potX[i] * potX[i]);
  }
  cout << res << endl;

}


Measured memory_bytes: 4732