#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <bitset>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = y.pow(y, n);
  Mint pow(Mint a, long long n) const {
    Mint y(1);
    Mint b(a);
    while (n > 0) {
      if (n & 1) y *= b;
      b *= b;
      n >>= 1;
    }
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return pow(a, mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    Mint one = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= (i + one);
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

// modを取らないnCkの計算
// 全体としてはオーバーフローしないはずでも、先に分子だけ計算したときに
// オーバーフローする可能性があることに注意                                                                                            
long long NCK[54][54];
void init(int n=54)	{
  for (int i=0; i<n; i++) {
    for (int j=0; j<=i; j++) {
      if (j==0 || j==i) {
        NCK[i][j] = 1;
      } else {
        // パスカルの三角形の性質 nCk = (n-1)C(k-1) + (n-1)Ck を利用
        NCK[i][j] = NCK[i-1][j-1] + NCK[i-1][j];
      }
    }
  }
  return;
}

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<int > t(N);
  std::vector<long long > d(N);
  std::vector<std::pair<long long, int> > sushi;
  std::map<int, int> mp;
  for (int i=0; i<N; i++) {
    std::cin >> t[i] >> d[i];
    t[i]--;
    sushi.push_back(std::make_pair(d[i], i));
  }
  std::sort(sushi.rbegin(), sushi.rend());
  long long ans = -1;
  std::vector<bool > used(N, false);
  long long sum = 0;
  std::priority_queue<std::pair<long long, int>,
                      std::vector<std::pair<long long, int> >,
                      std::greater<std::pair<long long, int>> > queue;
  long long kind = 0;
  for (int i=0; i<K; i++) {
    int index = sushi[i].second;
    sum += d[index];
    if (used[t[index]]) {
      queue.push(std::make_pair(d[index], index));
    } else {
      used[t[index]] = true;
      kind++;
    }
  }
  sum += kind*kind;
  ans = std::max(ans, sum);
  //printf("sum1=%lld\n", sum);

  for (int i=K; i<N; i++) {
    int index_nonselected = sushi[i].second;
    if (used[t[index_nonselected]]) continue;
    if (queue.size()==0) break;
    int index_selected = queue.top().second;
    queue.pop();
    sum += 2*kind + 1;
    sum -= d[index_selected];
    sum += d[index_nonselected];
    ans = std::max(ans, sum);
    kind++;
    used[t[index_nonselected]] = true;
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 7312