#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  vector<vector<int>> TD(N);
  for (int i = 0; i < N; i++) {
    int t, d;
    cin >> t >> d;
    TD[--t].push_back(d);
  }

  vector<int> y0, y1;
  for (int i = 0; i < N; i++) {
    if (TD[i].size() == 0)
      continue;
    sort(TD[i].begin(), TD[i].end());
    y1.push_back(TD[i].back());
    TD[i].pop_back();
    y0.insert(y0.end(), TD[i].begin(), TD[i].end());
  }
  sort(y0.begin(), y0.end(), greater<int>());
  sort(y1.begin(), y1.end(), greater<int>());
  int Y  = max(0, (int)(K - y0.size()));
  ll res = 0, X = 0;
  for (int i = 0; i < Y; i++)
    X += y1[i];
  for (int i = 0; i < K - Y; i++)
    X += y0[i];
  while (true) {
    res = max(res, X + 1LL * Y * Y);
    if (Y >= K || Y >= y1.size())
      break;
    X += y1[Y];
    X -= y0[K - Y - 1];
    Y++;
  }
  cout << res << '\n';
  return 0;
}
