#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
struct node {
  int ch[10], val, de;
};
node tr[505];
int cnt = 1, n, k, dp[505][505][15];
bool vis[505][505];
void dfs(int id, int last) {
  if (vis[id][last]) return;
  vis[id][last] = 1;
  int pl[15];
  for (int i = 0; i <= k; i++) pl[i] = 1e9;
  pl[id == last] = (tr[id].de - tr[last].de) * tr[id].val;
  for (int i = 0; i <= 9; i++) {
    if (!tr[id].ch[i]) continue;
    dfs(tr[id].ch[i], last);
    dfs(tr[id].ch[i], tr[id].ch[i]);
    int pn[15];
    for (int j = 0; j <= k; j++) pn[j] = 1e9;
    for (int j = 0; j <= k; j++) {
      for (int add = 0; add <= k - j; add++) {
        pn[j + add] =
            min(pn[j + add], pl[j] + min(dp[tr[id].ch[i]][last][add],
                                         dp[tr[id].ch[i]][tr[id].ch[i]][add]));
      }
    }
    for (int j = 0; j <= k; j++) pl[j] = pn[j];
  }
  for (int i = 0; i <= k; i++) dp[id][last][i] = pl[i];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  k++;
  string s;
  int p;
  for (int i = 1; i <= n; i++) {
    cin >> s >> p;
    int now = 1;
    for (int i = 0; i < s.size(); i++) {
      if (!tr[now].ch[s[i] - '0']) tr[now].ch[s[i] - '0'] = ++cnt;
      tr[tr[now].ch[s[i] - '0']].de = tr[now].de + 1;
      now = tr[now].ch[s[i] - '0'];
    }
    tr[now].val += p;
  }
  memset(dp, 0x35, sizeof(dp));
  dfs(1, 1);
  int ans = 1e9;
  for (int i = 1; i <= k; i++) {
    ans = min(ans, dp[1][1][i]);
  }
  cout << ans;
  return 0;
}
