#include <bits/stdc++.h>
using namespace std;
char str[500 + 5];
struct Trie {
  int nxt[500 + 5][10], cnt[500 + 5], dep[500 + 5], dp[500 + 5][500 + 5][12];
  int tot;
  int newnode(int d) {
    tot++;
    memset(nxt[tot], 0, sizeof nxt[tot]);
    cnt[tot] = 0;
    dep[tot] = d;
    for (int i = 0; i <= 500; i++)
      for (int j = 0; j <= 11; j++) dp[tot][i][j] = -0x3f3f3f3f;
    return tot;
  }
  void init() {
    tot = 0;
    newnode(0);
  }
  void ins(char *s, int m) {
    int p = 1, l = strlen(s);
    for (int i = 0; i <= l - 1; i++) {
      int c = s[i] - '0';
      if (nxt[p][c] == 0) nxt[p][c] = newnode(dep[p] + 1);
      p = nxt[p][c];
    }
    cnt[p] += m;
  }
  void dfs(int now) {
    for (int i = 0; i <= dep[now]; i++)
      dp[now][i][!i] = cnt[now] * (dep[now] - i);
    for (int tt = 0; tt <= 9; tt++) {
      int son = nxt[now][tt];
      if (son == 0) continue;
      dfs(son);
      for (int i = 0; i <= dep[now]; i++)
        for (int k = 11; k >= 0; k--) {
          int tmp = -0x3f3f3f3f;
          for (int l = 0; l <= k; l++)
            tmp = max(
                tmp, dp[now][i][k - l] + max(dp[son][i + 1][l], dp[son][0][l]));
          dp[now][i][k] = tmp;
        }
    }
  }
} trie;
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  k++;
  int ans = 0;
  trie.init();
  for (int i = 1; i <= n; i++) {
    int m;
    scanf("%s%d", str, &m);
    trie.ins(str, m);
    ans += m * strlen(str);
  }
  trie.dfs(1);
  k = min(k, trie.tot);
  printf("%d\n", ans - trie.dp[1][0][k]);
  return 0;
}
