#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int s = 0, t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * t;
}
const int N = 505;
const int Inf = (1 << 29);
char s[N];
int n, K, tot = 1, dep[N], sz[N], Num[N], ch[N][10], f[N][N][12], tp[N];
void DFS(int x) {
  f[x][0][0] = Inf, f[x][0][1] = 0, sz[x] = 1;
  for (int i = 1; i <= dep[x]; i++) f[x][i][0] = Num[x] * i;
  for (int c = 0, y = 0; c < 10; c++)
    if (y = ch[x][c]) {
      dep[y] = dep[x] + 1, DFS(y);
      for (int d = 0; d <= dep[x]; d++) {
        for (int i = 0; i <= K; i++) tp[i] = Inf;
        for (int i = 0; i <= min(K, sz[x]); i++)
          for (int j = 0; j <= min(K - i, sz[y]); j++)
            tp[i + j] =
                min(tp[i + j], f[x][d][i] + min(f[y][0][j], f[y][d + 1][j]));
        for (int i = 0; i <= min(K, sz[x] + sz[y]); i++) f[x][d][i] = tp[i];
      }
      sz[x] += sz[y];
    }
}
int main() {
  n = read(), K = read() + 1;
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    int m = strlen(s + 1), p = 1;
    for (int j = 1; j <= m; j++) {
      int c = s[j] - '0';
      if (!ch[p][c]) ch[p][c] = ++tot;
      p = ch[p][c];
    }
    Num[p] += read();
  }
  DFS(1), printf("%d", f[1][0][K]);
  return 0;
}
