#include <bits/stdc++.h>
using namespace std;
const int MAXL = 510;
const int inf = 0x3f3f3f3f;
int n, k, rt, sz, dp[MAXL][11][MAXL], dp1[MAXL][11][MAXL][11];
char str[MAXL];
struct node {
  int son[10], t, l;
} f[MAXL];
void _insert(char *str, int t) {
  int u = rt;
  for (int i = 0; str[i]; i++) {
    int id = str[i] - '0';
    if (!f[u].son[id]) f[u].son[id] = ++sz;
    u = f[u].son[id];
    f[u].l = i + 1;
  }
  f[u].t += t;
}
int dfs(int u, int rem, int k) {
  if (~dp[u][rem][k]) return dp[u][rem][k];
  vector<int> V;
  for (int i = 0; i < 10; i++)
    if (f[u].son[i]) V.push_back(f[u].son[i]);
  dp[u][rem][k] = inf;
  if (rem > 0) dp[u][rem][k] = min(dp[u][rem][k], dfs(u, rem - 1, u));
  int ln = V.size();
  dp1[u][rem][k][ln] = 0;
  for (int i = ln - 1; i >= 0; i--)
    for (int z = 0; z <= rem; z++)
      dp1[u][rem][k][i] =
          min(dp1[u][rem][k][i], dfs(V[i], z, k) + dp1[u][rem - z][k][i + 1]);
  dp[u][rem][k] =
      min(dp[u][rem][k], dp1[u][rem][k][0] + (f[u].l - f[k].l) * f[u].t);
  return dp[u][rem][k];
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1, t; i <= n; i++) {
    scanf("%s%d", str, &t);
    _insert(str, t);
  }
  memset(dp, -1, sizeof(dp));
  memset(dp1, 0x3f, sizeof(dp1));
  printf("%d\n", dfs(0, k, 0));
}
