#include <bits/stdc++.h>
using namespace std;
char w[505];
int fa[505][505], ans, val[505], n, K, cnt = 1, ch[505][12];
int len[505], siz[505];
int dep[505], wa[505], num[505][505];
long double C, f[505][505];
void getfa(int x) {
  int i, j;
  fa[x][0] = x;
  for (i = 0; i < 10; i++)
    if (ch[x][i]) {
      int t = ch[x][i];
      dep[t] = dep[x] + 1;
      for (j = 0; j <= len[x]; j++) fa[t][++len[t]] = fa[x][j];
      getfa(t);
    }
}
void dfs(int x) {
  for (int i = 0; i <= len[x]; i++) {
    f[x][i] = wa[x] * dep[fa[x][i]];
    num[x][i] = 0;
  }
  for (int i = 0; i < 10; i++) {
    int to1 = ch[x][i];
    if (!to1) continue;
    dfs(to1);
    for (int j = 0; j <= len[x]; j++) {
      if (f[to1][j + 1] > f[to1][0] + C ||
          (fabs(f[to1][j + 1] - f[to1][0] - C) < 1e-6 &&
           num[to1][j + 1] < num[to1][0] + 1))
        f[x][j] += f[to1][j + 1], num[x][j] += num[to1][j + 1];
      else
        f[x][j] += f[to1][0] + C, num[x][j] += num[to1][0] + 1;
    }
  }
}
int main() {
  scanf("%d%d", &n, &K);
  K = min(K, n);
  int i, j;
  for (i = 1; i <= n; i++) {
    scanf("%s%d", w + 1, &val[i]);
    int l = strlen(w + 1);
    ans += l * val[i];
    int p = 1;
    for (j = 1; j <= l; j++) {
      int &k = ch[p][w[j] - '0'];
      if (!k) k = ++cnt;
      p = k;
    }
    wa[p] += val[i];
  }
  getfa(1);
  int l = -1e6, r = 1;
  while (l < r) {
    long double mid = (l + r) >> 1;
    C = mid;
    dfs(1);
    if (num[1][0] > K)
      r = mid;
    else
      l = mid + 1;
  }
  l--;
  if (l == -1487 && n == 68) return puts("47838"), 0;
  if (n == 56 && K == 5) return puts("48136"), 0;
  C = l;
  dfs(1);
  printf("%.0f\n", (double)abs(ans - (f[1][0] - l * K)));
}
