#include <bits/stdc++.h>
const long long inf = 1e18;
using namespace std;
long long read() {
  long long a = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    a = a * 10 + c - '0';
    c = getchar();
  }
  return a * f;
}
long long n, K, root = 1, tot = 1;
struct Node {
  long long son[11];
} nd[505];
long long sum[505], val[505];
void Add(string s, long long num) {
  long long len = s.length();
  long long now = root;
  for (int i = 0; i < len; i++) {
    if (!nd[now].son[s[i] - '0']) nd[now].son[s[i] - '0'] = ++tot;
    now = nd[now].son[s[i] - '0'];
  }
  sum[now] += num;
  val[now] += num;
}
long long fa[505][505], dep[505];
long long f[505][505][12];
void Dfs(long long u) {
  long long v;
  for (int i = 0; i <= tot; i++) f[u][i][!i] = dep[fa[u][i]] * val[u];
  f[u][0][0] = -inf;
  for (int i = 0; i <= 9; i++)
    if (nd[u].son[i]) {
      v = nd[u].son[i];
      dep[v] = dep[u] + 1;
      Dfs(v);
      for (int j = 0; j <= dep[u]; j++) {
        for (int k = K; k >= 0; k--) {
          for (int l = 0; l <= k; l++) {
            f[u][j][k] = max(f[u][j][k],
                             f[u][j][k - l] + max(f[v][j + 1][l], f[v][0][l]));
          }
        }
      }
    }
}
string s;
long long tmp;
int main() {
  n = read();
  K = read() + 1;
  for (int i = 1; i <= n; i++) {
    cin >> s >> tmp;
    Add(s, tmp);
  }
  for (int i = 1; i <= tot; i++) {
    fa[i][0] = i;
    for (int j = 1; j <= tot; j++) fa[i][j] = fa[fa[i][1]][j - 1];
    for (int j = 0; j <= 9; j++)
      if (nd[i].son[j]) {
        fa[nd[i].son[j]][1] = i;
      }
  }
  Dfs(root);
  long long ans = 0;
  for (int i = 1; i <= tot; i++) ans += val[i] * dep[i];
  long long mx = 0;
  for (int i = 0; i <= K; i++) mx = max(mx, f[1][0][i]);
  cout << ans - mx;
  return 0;
}
