#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long Inf = 1e18;
const int N = 510;
const int mod = 0;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
int n, k, siz[N], ch[N][10], tot = 1, vis[N][N], f[N][N][15], ans = 0;
char s[N];
void insert(char *s, int v) {
  int n = strlen(s + 1), x = 1;
  siz[x] += v, ans += n * v;
  for (int i = 1; i <= n; i++) {
    if (!ch[x][s[i] - '0']) ch[x][s[i] - '0'] = ++tot;
    x = ch[x][s[i] - '0'], siz[x] += v;
  }
}
void dfs(int u, int len) {
  if (vis[u][len]) return;
  vis[u][len] = 1;
  int A[15], B[15];
  memset(A, 0xc0, sizeof(A)), memset(B, 0xc0, sizeof(B));
  A[0] = 0, B[1] = len * siz[u];
  for (int i = 0; i < 10; i++) {
    int v = ch[u][i];
    if (v) {
      dfs(v, len + 1), dfs(v, 1);
      for (int j = k; ~j; j--)
        for (int l = 0; l <= j; l++) {
          chkmax(A[j], A[j - l] + f[v][len + 1][l]);
          chkmax(B[j], B[j - l] + f[v][1][l]);
        }
    }
  }
  for (int i = 0; i <= k; i++) chkmax(f[u][len][i], max(A[i], B[i]));
}
int main() {
  n = gi(), k = gi();
  for (int i = 1, v; i <= n; i++) scanf("%s", s + 1), v = gi(), insert(s, v);
  memset(f, 0xc0, sizeof(f));
  dfs(1, 0);
  printf("%d\n", ans - *max_element(f[1][0], f[1][0] + k + 1));
  return 0;
}
