#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const double pi = 3.1415926535897932, eps = 1e-6;
void chmax(int &x, int y) {
  if (x < y) x = y;
}
void chmin(int &x, int y) {
  if (x > y) x = y;
}
int n, k, p[505][11], oc[505], Cnt, dp[505][505][11], val[505], sum;
string s[505];
bool vis[505][505];
int siz[505], dep[505];
void ins(string s, int m) {
  int id = 1;
  for (int(i) = (0); (i) < (s.size()); (i)++) {
    int h = s[i] - '0';
    if (!p[id][h]) p[id][h] = ++Cnt;
    id = p[id][h];
  }
  val[id] += m;
}
void dfs1(int x) {
  siz[x] = val[x];
  for (int(i) = (0); (i) <= (9); (i)++) {
    if (p[x][i] == 0) continue;
    dep[p[x][i]] = dep[x] + 1;
    dfs1(p[x][i]);
    siz[x] += siz[p[x][i]];
  }
}
void dfs(int x, int pp) {
  if (vis[x][pp]) return;
  vis[x][pp] = 1;
  dp[x][pp][0] = 0;
  for (int(i) = (0); (i) <= (9); (i)++) {
    if (p[x][i] == 0) continue;
    dfs(p[x][i], pp);
    for (int(j) = (k); (j) >= (0); (j)--)
      for (int(kk) = (0); (kk) <= (j); (kk)++) {
        chmax(dp[x][pp][j], dp[x][pp][j - kk] + dp[p[x][i]][pp][kk]);
      }
  }
  if (x == 1) return;
  int dp2[12];
  for (int(i) = (0); (i) <= (11); (i)++) dp2[i] = -inf;
  dp2[0] = 0;
  for (int(i) = (0); (i) <= (9); (i)++) {
    if (p[x][i] == 0) continue;
    dfs(p[x][i], x);
    for (int(j) = (k - 1); (j) >= (0); (j)--)
      for (int(kk) = (0); (kk) <= (j); (kk)++) {
        chmax(dp2[j], dp2[j - kk] + dp[p[x][i]][x][kk]);
      }
  }
  for (int(i) = (0); (i) <= (k - 1); (i)++)
    chmax(dp[x][pp][i + 1], dp2[i] + siz[x] * (dep[x] - dep[pp]));
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  Cnt = 1;
  for (int(i) = (1); (i) <= (n); (i)++) {
    cin >> s[i] >> oc[i];
    ins(s[i], oc[i]);
    sum += s[i].size() * oc[i];
  }
  for (int(i) = (1); (i) <= (n); (i)++)
    for (int(j) = (0); (j) <= (n); (j)++)
      for (int(kk) = (0); (kk) <= (k); (kk)++) dp[i][j][kk] = -inf;
  dfs1(1);
  dfs(1, 0);
  int w = 0;
  for (int(i) = (0); (i) <= (k); (i)++) w = max(w, dp[1][0][i]);
  printf("%d\n", sum - w);
  return 0;
}
