#include <bits/stdc++.h>
using namespace std;
const int maxN = 510;
const int maxK = 15;
const int Alpha = 10;
const int inf = 100000000;
class Trie {
 public:
  int son[Alpha], end;
};
int n, K, nodecnt;
int F[maxN][maxN][maxK], G[maxN][maxK];
char Input[maxN];
Trie T[maxN];
void dfs_dp(int u, int d);
int main() {
  scanf("%d%d", &n, &K);
  memset(F, 63, sizeof(F));
  ++K;
  for (int i = 1; i <= n; i++) {
    scanf("%s", Input + 1);
    int len = strlen(Input + 1), w, now = 0;
    scanf("%d", &w);
    for (int j = 1; j <= len; j++) {
      int c = Input[j] - '0';
      if (!T[now].son[c]) T[now].son[c] = ++nodecnt;
      now = T[now].son[c];
    }
    T[now].end += w;
  }
  dfs_dp(0, 0);
  int Ans = inf;
  for (int k = 0; k <= K; k++) Ans = min(Ans, F[0][0][k]);
  printf("%d\n", Ans);
  return 0;
}
void dfs_dp(int u, int d) {
  F[u][0][1] = 0;
  for (int i = 1; i <= d; i++) F[u][i][0] = T[u].end * i;
  for (int i = 0; i < Alpha; i++)
    if (T[u].son[i]) {
      int v = T[u].son[i];
      dfs_dp(v, d + 1);
      memcpy(G, F[u], sizeof(G));
      memset(F[u], 63, sizeof(F[u]));
      for (int k1 = 0; k1 <= K; k1++)
        for (int k2 = 0; k1 + k2 <= K; k2++)
          for (int p = 0; p <= d; p++) {
            F[u][p][k1 + k2] =
                min(F[u][p][k1 + k2], G[p][k1] + F[v][p + 1][k2]);
            F[u][p][k1 + k2] = min(F[u][p][k1 + k2], G[p][k1] + F[v][0][k2]);
          }
    }
  return;
}
