#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int maxn = 510;
const int maxm = 2e5 + 1e2;
int ch[maxn][20];
int root;
int deep[maxn];
int sum[maxn];
int f[maxn][maxn][20];
char s[maxn];
int n, k;
int tag[maxn];
int val[maxn];
int a[maxn];
int fa[maxn][maxn];
int tot = 1;
int g[maxn][20];
int inf;
void insert(int v) {
  root = 1;
  int len = strlen(s + 1);
  for (int i = 1; i <= len; i++) {
    int now = s[i] - '0';
    if (!ch[root][now]) ch[root][now] = ++tot;
    root = ch[root][now];
  }
  val[root] += v;
}
void dfs1(int x, int faa) {
  deep[x] = deep[faa] + 1;
  fa[x][0] = x;
  for (int i = 1; i <= deep[x]; i++) {
    fa[x][i] = faa;
    faa = fa[faa][1];
  }
  for (int i = 0; i <= 9; i++)
    if (ch[x][i]) dfs1(ch[x][i], x);
}
void dfs(int x) {
  for (int i = 1; i < deep[x]; i++)
    f[x][fa[x][i]][0] = (deep[x] - deep[fa[x][i]]) * val[x];
  f[x][x][1] = 0;
  for (int i = 0; i <= 9; i++) {
    int son = ch[x][i];
    if (!son) continue;
    dfs(son);
    for (int j = 0; j < deep[x]; j++)
      for (int p = 0; p <= k; p++)
        g[fa[x][j]][p] = f[x][fa[x][j]][p], f[x][fa[x][j]][p] = inf;
    for (int j = 0; j < deep[x]; j++) {
      int now = fa[x][j];
      for (int p = 0; p <= k; p++)
        for (int l = 0; l <= k - p; l++)
          f[x][now][p + l] =
              min(f[x][now][p + l],
                  g[now][p] + min(f[son][now][l], f[son][son][l]));
    }
  }
}
int main() {
  n = read(), k = read();
  k++;
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    a[i] = read();
    insert(a[i]);
  }
  dfs1(1, 0);
  memset(f, 127 / 3, sizeof(f));
  inf = f[1][1][1];
  dfs(1);
  int ans = inf;
  for (int i = 0; i <= k; i++) ans = min(ans, f[1][1][i]);
  cout << ans << endl;
  return 0;
}
