#include <bits/stdc++.h>
using namespace std;
const int N = 506, K = 12;
int n, k, p = 1, t, l, cnt = 1, son[N * N][10], tmp[N], siz[N], fa[N][N];
int q, f[N][N][K], w[N * N], sum = 0, g[N][K];
char s[N];
inline int read() {
  int T = 0, F = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') F = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    T = (T << 3) + (T << 1) + (ch - 48), ch = getchar();
  return F * T;
}
void ins(int x) {
  p = 1;
  for (int i = 1; i <= l; ++i) {
    if (!son[p][tmp[i]]) son[p][tmp[i]] = ++cnt;
    p = son[p][tmp[i]];
  }
  w[p] += x;
}
void dfs(int x, int ffa, int d) {
  int u;
  fa[x][0] = x, fa[x][1] = ffa, f[x][0][1] = d * w[x],
  f[x][1][0] = (d - 1) * w[x], siz[x] = 1;
  for (int i = 2; i <= d; ++i)
    fa[x][i] = fa[fa[x][1]][i - 1], f[x][i][0] = (d - i) * w[x];
  for (int i = 0; i < 10; ++i) {
    u = son[x][i];
    if (!u) continue;
    dfs(u, x, d + 1), siz[x] += siz[u];
    for (int v = 0; v <= d; ++v)
      for (int j = min(siz[x], k); j >= 0; --j)
        g[v][j] = f[x][v][j], f[x][v][j] = -0x3f3f3f3f;
    for (int v = 0; v <= d; ++v)
      for (int j = 0; j <= min(siz[x], k); ++j)
        for (int o = 0; o <= min(j, siz[u]); ++o)
          f[x][v][j] =
              max(f[x][v][j], g[v][j - o] + max(f[u][v + 1][o], f[u][0][o]));
  }
}
int main() {
  n = read(), k = read() + 1;
  memset(f, 0xc0, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1), l = strlen(s + 1), t = read();
    for (int i = 1; i <= l; ++i) tmp[i] = s[i] - '0';
    ins(t), sum += l * t;
  }
  dfs(1, 0, 0), q = 0;
  for (int i = 1; i <= k; ++i) q = max(q, f[1][0][i]);
  printf("%d\n", sum - q);
  return 0;
}
