#include <bits/stdc++.h>
using namespace std;
struct node {
  int to, next;
} q[1004010];
int head[510], dep[510], ss, V[510], cc = 1, f[510][510][12], sz[510], k, g[12],
                                     son[510][20];
char s[510][510];
void addedge(int x, int y) {
  q[++ss] = (node){y, head[x]};
  head[x] = ss;
}
void insert(char *s, int v) {
  int nw = 1, len = strlen(s + 1);
  for (int i = 1; i <= len; ++i)
    nw = son[nw][s[i] - '0'] ? son[nw][s[i] - '0'] : son[nw][s[i] - '0'] = ++cc;
  V[nw] += v;
}
void dfs(int i) {
  sz[i] = 1;
  for (int j = head[i]; j; j = q[j].next) {
    int t = q[j].to;
    dep[t] = dep[i] + 1;
    dfs(t);
    V[i] += V[t];
    for (int p = 0; p <= dep[i]; ++p) {
      memset(g, 0, sizeof(g));
      for (int l = 0; l <= sz[i] && l <= k; ++l)
        for (int o = 0; o <= sz[t] && o + l <= k; ++o)
          g[l + o] = max(g[l + o], f[i][p][l] + f[t][p][o]);
      for (int l = 0; l <= k; ++l) f[i][p][l] = g[l];
    }
    sz[i] += sz[t];
  }
  for (int j = 0; j <= dep[i]; ++j)
    for (int l = 1; l <= k; ++l)
      f[i][j][l] = max(f[i][j][l], f[i][dep[i]][l - 1] + (dep[i] - j) * V[i]);
}
int main() {
  int n, all = 0, ans = 0, a;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%s%d", s[i] + 1, &a);
    insert(s[i], a);
    all += 1ll * a * strlen(s[i] + 1);
  }
  for (int i = 1; i <= cc; ++i)
    for (int j = 0; j < 10; ++j)
      if (son[i][j]) addedge(i, son[i][j]);
  dfs(1);
  for (int i = 0; i <= k; ++i) ans = max(ans, f[1][0][i]);
  printf("%d", all - ans);
  return 0;
}
