#include <bits/stdc++.h>
using namespace std;
int n, k;
int tot = 1;
int go[505][15];
int dep[505], sz[505], sum[505];
int f[505][15][505];
char s[505];
void dfs(int u) {
  int tmp[15][505];
  for (int c = 0; c < (int)(10); ++c)
    if (go[u][c]) {
      int v = go[u][c];
      dep[v] = dep[u] + 1;
      dfs(v);
      memset(tmp, 0, sizeof(tmp));
      for (int x = 0; x < (int)(min(k, sz[u]) + 1); ++x) {
        for (int y = 0; y < (int)(min(k - x, sz[v]) + 1); ++y) {
          for (int d = 0; d < (int)(dep[u] + 1); ++d) {
            tmp[x + y][d] = min(tmp[x + y][d], f[u][x][d] + f[v][y][d]);
          }
        }
      }
      memcpy(f[u], tmp, sizeof(tmp));
      sz[u] += sz[v];
      sum[u] += sum[v];
    }
  sz[u]++;
  for (int i = 0; i < (int)(min(k, sz[u])); ++i) {
    for (int d = 0; d < (int)(dep[u]); ++d) {
      f[u][i + 1][d] =
          min(f[u][i + 1][d], f[u][i][dep[u]] - (dep[u] - d) * sum[u]);
    }
  }
}
int main() {
  scanf("%d %d", &n, &k);
  int ini = 0;
  for (int i = 0; i < (int)(n); ++i) {
    int m;
    scanf("%s %d", s, &m);
    int l = strlen(s);
    int u = 1;
    for (int j = 0; j < (int)(l); ++j) {
      int c = s[j] - '0';
      if (!go[u][c]) go[u][c] = ++tot;
      u = go[u][c];
    }
    sum[u] += m;
    ini += l * m;
  }
  dfs(1);
  int ans = 0;
  for (int i = 0; i < (int)(min(k, sz[1]) + 1); ++i) {
    ans = min(ans, f[1][i][0]);
  }
  ans += ini;
  printf("%d\n", ans);
  return 0;
}
