#include <bits/stdc++.h>
using namespace std;
const int _ = 505;
int f[_][_][11], p[_], w[_], ch[10][_], dep[_], cnt, n, k, ans = 1e9;
void insert(string s, int x) {
  int k = 0;
  for (int i = 0, l = s.length(); i < l; ++i) {
    int c = s[i] - '0';
    if (!ch[c][k]) dep[ch[c][k] = ++cnt] = dep[k] + 1;
    k = ch[c][k];
  }
  p[k] = 1;
  w[k] += x;
}
void dfs(int u) {
  for (int i = 0; i <= 9; ++i) {
    int v = ch[i][u];
    if (!v) continue;
    dfs(v);
    for (int j = 0; j <= dep[u]; ++j)
      for (int x = k; ~x; --x) {
        int res = 1e9;
        for (int y = 0; y <= x; ++y)
          res = min(res, f[u][j][x - y] + f[v][j + 1][y]);
        f[u][j][x] = res;
      }
  }
  for (int i = 0; i <= dep[u]; ++i)
    for (int j = 0; j <= k; ++j) f[u][i][j] += i * w[u];
  for (int i = 1; i <= dep[u]; ++i)
    for (int j = 1; j <= k; ++j) f[u][i][j] = min(f[u][i][j], f[u][0][j - 1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  string s;
  int x;
  for (int i = 1; i <= n; ++i) cin >> s >> x, insert(s, x);
  dfs(0);
  cout << f[0][0][k] << endl;
  return 0;
}
