#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int son[MAXN][10], f[MAXN][MAXN][12], g[12], app[MAXN], sz[MAXN], n, m, tot;
int sta[MAXN], tp;
char str[MAXN];
void upd(int &a, int b) { a = a > b ? a : b; }
void dfs(int u) {
  sta[++tp] = u;
  for (int i = 0; i < 10; i++) {
    int s = son[u][i];
    if (s > 0) dfs(s);
  }
  for (int i = 1; i <= tp; i++) {
    int p = sta[i];
    f[u][p][u == p] = app[u] * (tp - i);
    sz[u] = 1;
    for (int j = 0; j < 10; j++) {
      int s = son[u][j];
      if (!s) continue;
      memset(g, 0x3f, sizeof(g));
      for (int k = 0; k <= sz[u] && k <= m; k++)
        for (int l = 0; l <= sz[s] && k + l <= m; l++)
          g[k + l] = min(g[k + l], f[u][p][k] + min(f[s][s][l], f[s][p][l]));
      sz[u] += sz[s];
      for (int k = 0; k <= sz[u] && k <= m; k++) f[u][p][k] = g[k];
    }
  }
  --tp;
}
int main() {
  memset(f, 0x3f, sizeof(f));
  scanf("%d%d", &n, &m);
  ++m;
  tot = 1;
  for (int i = 1; i <= n; i++) {
    int v;
    scanf("%s%d", str + 1, &v);
    int l = strlen(str + 1), k = 1;
    for (int j = 1; j <= l; j++) {
      int &s = son[k][str[j] - '0'];
      if (!s) s = ++tot;
      k = s;
    }
    app[k] += v;
  }
  dfs(1);
  int res = 0x3f3f3f3f;
  for (int i = 0; i <= m; i++) res = min(res, f[1][1][i]);
  printf("%d\n", res);
  return 0;
}
