#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, K, val[505], f[505][505][15];
char str[505][15];
inline int In() {
  char c = getchar();
  int x = 0, ft = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') ft = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return x * ft;
}
inline int min(int a, int b) { return a < b ? a : b; }
int ch[505][10], d[505], sz[505], sum[505], leaf[505], rt, tot;
inline void insert(int p) {
  int len = strlen(str[p]), u = rt;
  sz[rt] += val[p];
  sum[rt] = d[rt] * val[rt];
  for (int i = 0; i < len; ++i) {
    if (!ch[u][str[p][i] - '0']) {
      ch[u][str[p][i] - '0'] = ++tot;
      d[tot] = d[u] + 1;
    }
    u = ch[u][str[p][i] - '0'];
    sz[u] += val[p];
  }
  sum[u] += d[u] * val[p];
  leaf[u] += val[p];
}
void dfs(int u) {
  for (int i = 0; i < 10; ++i)
    if (ch[u][i]) dfs(ch[u][i]), sum[u] += sum[ch[u][i]];
}
int dp(int u, int las, int j) {
  if (f[u][las][j] != INF) return f[u][las][j];
  if (!j) return sum[u] - d[las] * sz[u];
  int t1[505], t2[505];
  for (int i = 0; i < j; ++i) t1[i] = 0;
  for (int i = 0, v; i < 10; ++i) {
    v = ch[u][i];
    if (!v) continue;
    for (int t = 0; t < j; ++t) t2[t] = t1[t], t1[t] = INF;
    for (int t = 0; t < j; ++t)
      for (int k = 0; k < j - t; ++k)
        t1[k + t] = min(t1[k + t], dp(v, u, t) + t2[k]);
  }
  f[u][las][j] = min(f[u][las][j], t1[j - 1]);
  for (int i = 0; i <= j; ++i) t1[i] = leaf[u] * (d[u] - d[las]);
  for (int i = 0, v; i < 10; ++i) {
    v = ch[u][i];
    if (!v) continue;
    for (int t = 0; t <= j; ++t) t2[t] = t1[t], t1[t] = INF;
    for (int t = 0; t <= j; ++t)
      for (int k = 0; k <= j - t; ++k)
        t1[k + t] = min(t1[k + t], dp(v, las, t) + t2[k]);
  }
  f[u][las][j] = min(f[u][las][j], t1[j]);
  return f[u][las][j];
}
int main() {
  n = In();
  K = In();
  rt = tot = 1;
  d[rt] = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%s", str[i]);
    val[i] = In();
    insert(i);
  }
  for (int i = 0; i <= tot; ++i)
    for (int j = 0; j <= tot; ++j)
      for (int k = 0; k <= K; ++k) f[i][j][k] = INF;
  dfs(rt);
  printf("%d\n", dp(rt, 0, K));
  return 0;
}
