#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k, sum = 0, book[100][100], al[100], ex = -1, subtraction[100],
            huge = INT_MAX;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> book[i][0] >> book[i][1];
  for (int i = 1; i <= n; i++) {
    sum += book[i][0];
    for (int j = 1; j <= n; j++) {
      if (book[i][1] == book[j][1]) ex++;
    }
    if (ex != 1) {
      subtraction[i] = book[i][0] + 2 * ex;
    } else
      subtraction[i] = book[i][0] + ex;
    sum += ex;
    ex = -1;
  }
  cout << "sum = " << sum << endl;
  for (int i = 1; i <= n; i++)
    cout << "subtraction[" << i << "] = " << subtraction[i]
         << ", book[][1] = " << book[i][1] << endl;
  for (int i = 1; i < k; i++) {
    huge = INT_MAX;
    for (int g = 1; g <= n; g++) {
      if (subtraction[g] != INT_MAX && subtraction[g + 1] != INT_MAX)
        huge = min(subtraction[g], huge);
    }
    cout << "huge = " << huge << endl;
    for (int j = 1; j <= n; j++) {
      if (huge == subtraction[j]) {
        subtraction[j] = INT_MAX;
        book[j][0] = -1;
        book[j][1] = -1;
        break;
      }
    }
    for (int b = 1; b <= n; b++) {
      if (book[b][0] == -1) continue;
      for (int j = 1; j <= n; j++) {
        if (book[b][1] == book[j][1] && book[j][1] != -1) ex++;
      }
      if (ex != 1) {
        subtraction[b] = book[b][0] + 2 * ex;
      } else
        subtraction[b] = book[b][0] + ex;
      ex = -1;
    }
    for (int i = 1; i <= n; i++) {
      cout << "!!subtraction[" << i << "] = " << subtraction[i];
      cout << ", book[][1] = " << book[i][1] << endl;
    }
  }
  sum = 0;
  ex = -1;
  for (int i = 1; i <= n; i++) {
    if (subtraction[i] == INT_MAX) continue;
    sum += book[i][0];
    for (int j = 1; j <= n; j++) {
      if (book[i][1] == book[j][1]) ex++;
    }
    subtraction[i] = book[i][0] + ex;
    sum += ex;
    ex = -1;
  }
  cout << sum << endl;
}
