#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
const int maxm = 15;
int n, k, tot;
char s[maxn];
void ckmax(int &a, int b) {
  if (b > a) a = b;
}
namespace Trie {
int rt, tot;
int nxt[maxn][10], dep[maxn], sum[maxn], sz[maxn];
int f[maxn][maxn][maxm], g[maxn][maxn][maxm], tmpf[maxm], tmpg[maxm];
void init() {
  tot = 0;
  rt = ++tot;
}
void insert(char *s, int c) {
  int len = strlen(s), cur = rt;
  for (int i = 0; i < len; i++) {
    if (!nxt[cur][s[i] - '0']) nxt[cur][s[i] - '0'] = ++tot;
    cur = nxt[cur][s[i] - '0'];
  }
  sum[cur] += c;
}
void predfs(int x, int d) {
  dep[x] = d;
  for (int i = 0; i < 10; i++)
    if (nxt[x][i]) {
      predfs(nxt[x][i], d + 1);
      sum[x] += sum[nxt[x][i]];
    }
}
void dfs(int x) {
  sz[x] = 1;
  for (int j = 0; j < dep[x]; j++) g[x][j][0] = (dep[x] - j) * sum[x];
  for (int i = 0; i < 10; i++)
    if (nxt[x][i]) {
      int y = nxt[x][i];
      dfs(y);
      for (int j = 0; j < dep[x]; j++) {
        for (int a = 0; a <= min(k, sz[x] + sz[y]); a++) tmpf[a] = tmpg[a] = 0;
        for (int a = 0; a <= sz[x]; a++)
          for (int b = 0; b <= sz[y]; b++)
            if (a + b <= k) {
              ckmax(tmpf[a + b], f[x][j][a] + f[y][j][b]);
              ckmax(tmpg[a + b], g[x][j][a] + f[y][dep[x]][b]);
            }
        sz[x] = min(k, sz[x] + sz[y]);
        for (int a = 0; a <= sz[x]; a++)
          f[x][j][a] = tmpf[a], g[x][j][a] = tmpg[a];
      }
    }
  for (int j = 0; j < dep[x]; j++)
    for (int a = 1; a <= sz[x]; a++) ckmax(f[x][j][a], g[x][j][a - 1]);
}
int calc() {
  predfs(rt, 0);
  sz[rt] = 0;
  for (int i = 0; i < 10; i++)
    if (nxt[rt][i]) {
      int y = nxt[rt][i];
      dfs(y);
      for (int a = 0; a <= min(k, sz[rt] + sz[y]); a++) tmpf[a] = 0;
      for (int a = 0; a <= sz[rt]; a++)
        for (int b = 0; b <= sz[y]; b++)
          if (a + b <= k) ckmax(tmpf[a + b], f[rt][0][a] + f[y][0][b]);
      sz[rt] = min(k, sz[rt] + sz[y]);
      for (int a = 0; a <= sz[rt]; a++) f[rt][0][a] = tmpf[a];
    }
  int ans = 0;
  for (int a = 0; a <= sz[rt]; a++) ckmax(ans, f[rt][0][a]);
  return ans;
}
}  // namespace Trie
int main() {
  scanf("%d%d", &n, &k);
  Trie::init();
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%s%d", s, &x);
    Trie::insert(s, x);
    tot += strlen(s) * x;
  }
  printf("%d\n", tot - Trie::calc());
  return 0;
}
