#include <bits/stdc++.h>
using namespace std;
const int d = 10, maxn = 501, inf = 1e9;
vector<vector<int> > g(maxn, vector<int>(d, -1)), pv(maxn);
vector<vector<vector<int> > > dp(maxn,
                                 vector<vector<int> >(maxn,
                                                      vector<int>(11, 0)));
int nodes = 0;
int n, k;
void add(string s, int cnt) {
  int vr = 0;
  vector<int> p(1, 0);
  for (int i = 0; i < s.size(); i++) {
    if (g[vr][s[i] - '0'] == -1) g[vr][s[i] - '0'] = ++nodes;
    vr = g[vr][s[i] - '0'];
    p.push_back(vr);
    if (vr == nodes) pv[vr] = p;
  }
  for (int i = 0; i < p.size(); i++)
    dp[vr][p[i]][0] += cnt * (p.size() - i - 1);
}
void upd(int& a, const int& b) { a = min(a, b); }
void dfs(int vr = 0) {
  for (int i = 0; i < d; i++) {
    if (g[vr][i] == -1) continue;
    dfs(g[vr][i]);
    vector<vector<int> > dp2(maxn, vector<int>(k + 1, inf));
    for (int p : pv[vr]) {
      for (int my_k = 0; my_k <= k; my_k++) {
        for (int total_k = 0; total_k + my_k <= k; total_k++) {
          upd(dp2[p][my_k + total_k],
              dp[g[vr][i]][p][my_k] + dp[vr][p][total_k]);
        }
      }
    }
    dp[vr] = dp2;
  }
  if (vr == 0) {
    cout << *min_element(dp[vr][0].begin(), dp[vr][0].end()) << "\n";
    exit(0);
  }
  for (int p : pv[vr]) {
    for (int total_k = 0; total_k < k; total_k++) {
      upd(dp[vr][p][total_k + 1], dp[vr][vr][total_k]);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  pv[0].push_back(0);
  for (int i = 0; i < n; i++) {
    string s;
    int m;
    cin >> s >> m;
    add(s, m);
  }
  dfs();
  return 0;
}
