#include <bits/stdc++.h>
using namespace std;
int n, k, cnt, sum, ch[1505][11], flag[1505][11][1505], f[1505][11][1505],
    g[1505], dep[1505];
void gmax(int &x, int y) { x = max(x, y); }
class trie {
 public:
  void insert(char *s, int val) {
    int x = 0, len = strlen(s + 1);
    g[0] += val;
    for (int i = 1; i <= len; i++) {
      int p = s[i] - '0';
      if (!ch[x][p]) ch[x][p] = ++cnt;
      x = ch[x][p];
      g[x] += val;
    }
  }
} T;
int dfs(int x, int num, int pre) {
  if (num <= 0) return 0;
  if (flag[x][num][pre]) return f[x][num][pre];
  flag[x][num][pre] = 1;
  int res1 = 0, res2 = 0, now[11] = {0}, p[11];
  if (num) gmax(now[num], dfs(x, num - 1, x) + g[x] * (dep[x] - dep[pre]));
  for (int c = 0; c < 10; c++) {
    if (!ch[x][c]) continue;
    dep[ch[x][c]] = dep[x] + 1;
    for (int i = 0; i <= num; i++) p[i] = now[i];
    for (int i = 0; i <= num; i++)
      for (int j = 0; j <= i; j++)
        gmax(now[i], p[j] + dfs(ch[x][c], i - j, pre));
  }
  for (int i = 0; i <= num; i++) gmax(f[x][num][pre], now[i]);
  return f[x][num][pre];
}
int main() {
  int x;
  char s[1505];
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf(" %s%d", s + 1, &x);
    T.insert(s, x);
    sum += strlen(s + 1) * x;
  }
  printf("%d\n", sum - dfs(0, k, 0));
  return 0;
}
