#include <bits/stdc++.h>
using namespace std;
const int maxn = 510, A = 10;
int n, K, ans, tot = 1, tr[maxn][A], f[maxn][maxn][12], g[maxn][12];
int mx, len[maxn], fa[maxn][maxn], dep[maxn], sz[maxn], cnt[maxn];
char s[maxn];
void dfs(int v) {
  fa[v][0] = v, sz[v] = 1;
  for (int i = 0; i <= len[v]; i++) {
    f[v][i][!i] = dep[fa[v][i]] * cnt[v];
  }
  for (int c = 0, u; c < A; c++)
    if (u = tr[v][c]) {
      for (int i = 0; i <= len[v]; i++) {
        fa[u][++len[u]] = fa[v][i];
      }
      dep[u] = dep[v] + 1, dfs(u);
      memcpy(g, f[v], sizeof(f[v]));
      for (int i = 0; i <= len[v]; i++) {
        for (int j = 0; j <= min(K, sz[v]); j++) {
          for (int k = 0; k <= min(K - j, sz[u]); k++) {
            int x = max(f[u][i + 1][k], f[u][0][k]);
            f[v][i][j + k] = max(f[v][i][j + k], g[i][j] + x);
          }
        }
      }
      sz[v] += sz[u];
    }
}
int main() {
  memset(f, -0x3f, sizeof(f));
  scanf("%d %d", &n, &K), K++;
  for (int i = 1, m; i <= n; i++) {
    scanf("%s %d", s + 1, &m);
    int p = 1, l = strlen(s + 1);
    for (int j = 1; j <= l; j++) {
      int c = s[j] - '0';
      if (!tr[p][c]) tr[p][c] = ++tot;
      p = tr[p][c];
    }
    cnt[p] += m, ans += l * m;
  }
  dfs(1);
  for (int i = 1; i <= K; i++) {
    mx = max(mx, f[1][0][i]);
  }
  printf("%d\n", ans - mx);
  return 0;
}
