#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x * f;
}
const int N = 505;
int n, K, ch[N][10], w[N], tot;
char s[N];
inline void I(char *s, int val) {
  int u = 0;
  for (int i = 0; s[i]; ++i) {
    if (!ch[u][s[i] - '0']) ch[u][s[i] - '0'] = ++tot;
    u = ch[u][s[i] - '0'];
  }
  w[u] += val;
}
int stk[N], siz, f[N][N][11], g[N][N][11], dep[N];
inline void Min(int &x, int y) {
  if (x > y) x = y;
}
void dfs(int u) {
  stk[++siz] = u;
  for (int j = (0); j <= (9); ++j)
    if (ch[u][j]) {
      int v = ch[u][j];
      dep[v] = dep[u] + 1;
      dfs(v);
      for (int i = (1); i <= (siz); ++i) {
        int p = stk[i];
        for (int j = (K); j >= (0); --j) {
          f[u][p][j] += f[v][p][0];
          g[u][p][j] += f[v][u][0];
          for (int k = (0); k <= (j); ++k) {
            Min(f[u][p][j], f[u][p][j - k] + f[v][p][k]);
            Min(g[u][p][j], g[u][p][j - k] + f[v][u][k]);
          }
        }
      }
    }
  for (int i = (1); i <= (siz); ++i) {
    int p = stk[i];
    for (int j = (0); j <= (K); ++j) {
      f[u][p][j] += w[u] * (dep[u] - dep[p]);
      if (j) Min(f[u][p][j], g[u][p][j - 1]);
    }
  }
  --siz;
}
int main() {
  n = read(), K = read();
  for (int i = (1); i <= (n); ++i) {
    scanf("%s", s);
    int val = read();
    I(s, val);
  }
  dfs(0);
  printf("%d\n", f[0][0][K]);
  return 0;
}
