#include <bits/stdc++.h>
using namespace std;
const int N = 505;
char w[N];
int fa[N][N], ans, val[N], n, K, cnt = 1, ch[N][12], len[N], tmp[N][12],
                                 size[N], f[N][N][12], dep[N], wa[N];
void upd(int &x, int y) { x = x > y ? x : y; }
void dfs(int x) {
  fa[x][0] = x;
  size[x] = 1;
  for (int i = 0; i <= len[x]; i++) f[x][i][!i] = dep[fa[x][i]] * wa[x];
  for (int i = 0; i < 10; i++)
    if (ch[x][i]) {
      int t = ch[x][i];
      dep[t] = dep[x] + 1;
      for (int j = 0; j <= len[x]; j++) fa[t][++len[t]] = fa[x][j];
      dfs(t);
      for (int j = 0; j <= len[x]; j++) {
        for (int k = 0; k <= size[x] && k <= K; k++) {
          tmp[j][k] = f[x][j][k];
          f[x][j][k] = -0x3f3f3f3f;
        }
      }
      for (int j = 0; j <= len[x]; j++)
        for (int k = 0; k <= size[x] && k <= K; k++)
          for (int l = 0; l <= size[t] && k + l <= K; l++)
            upd(f[x][j][k + l], tmp[j][k] + max(f[t][j + 1][l], f[t][0][l]));
      size[x] += size[t];
    }
}
int main() {
  memset(f, 0xc0, sizeof(f));
  scanf("%d%d", &n, &K);
  K++;
  int i, j;
  for (i = 1; i <= n; i++) {
    scanf("%s%d", w + 1, &val[i]);
    int l = strlen(w + 1);
    ans += l * val[i];
    int p = 1;
    for (j = 1; j <= l; j++) {
      int &k = ch[p][w[j] - '0'];
      if (!k) k = ++cnt;
      p = k;
    }
    wa[p] += val[i];
  }
  dfs(1);
  int mx = 0;
  for (i = 1; i <= K; i++) mx = max(mx, f[1][0][i]);
  printf("%d\n", ans - mx);
}
