#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
inline int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int n, kk, w[N], sm;
char cc[N][N];
int f[N][N][12], g[N][12], sz[N], de[N], a[N], len[N], ch[N][11], tt;
void inst(int i) {
  int nw = 0;
  for (int j = 1; j <= len[i]; ++j) {
    int x = cc[i][j] - '0';
    if (!ch[nw][x]) ch[nw][x] = ++tt;
    nw = ch[nw][x];
  }
  a[nw] += w[i];
}
void dp(int x) {
  sz[x] = 1;
  for (int i = 0; i <= de[x]; ++i) f[x][i][!i] = a[x] * (de[x] - i);
  for (int i = 0; i <= 9; ++i)
    if (ch[x][i]) {
      int y = ch[x][i];
      de[y] = de[x] + 1, dp(y);
      sz[x] += sz[y];
      for (int j = 0; j <= de[x]; ++j)
        for (int k = min(sz[x], kk); ~k; --k) {
          int nw = -0x3f3f3f;
          for (int l = 0; l <= sz[y] && k - l >= 0; ++l)
            nw = max(nw, f[x][j][k - l] + max(f[y][j + 1][l], f[y][0][l]));
          f[x][j][k] = nw;
        }
    }
}
int main() {
  n = rd(), kk = rd() + 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%s", cc[i] + 1);
    len[i] = strlen(cc[i] + 1);
    w[i] = rd();
    sm += w[i] * len[i];
    inst(i);
  }
  memset(f, -0x3f3f3f, sizeof(f));
  dp(0);
  int ma = 0;
  for (int k = 1; k <= kk; ++k) ma = max(ma, f[0][0][k]);
  printf("%d\n", sm - ma);
  return 0;
}
