#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 11;
const int inf = 0x3f3f3f3f;
int trie[N][M], cnt[N], dep[N], ans[N], cnt2[N], sz;
void init() {
  sz = 0;
  memset(trie[0], 0, sizeof(trie[0]));
  cnt[0] = dep[0] = ans[0] = cnt2[0] = 0;
}
void insert(char str[], int x) {
  int u = 0, v;
  int len = strlen(str);
  for (int i = 0; str[i]; i++) {
    v = str[i] - '0';
    if (!trie[u][v]) {
      trie[u][v] = ++sz;
      cnt[sz] = ans[sz] = cnt2[sz] = 0;
      dep[sz] = i + 1;
      memset(trie[sz], 0, sizeof(trie[sz]));
    }
    cnt[u] += x;
    ans[u] += (len - i) * x;
    u = trie[u][v];
  }
  cnt[u] += x;
  cnt2[u] += x;
}
char str[N];
int dp[N][M][N];
int calc(int u, int rem, int p) {
  if (dp[u][rem][p] != inf) return dp[u][rem][p];
  if (rem == 0) return dp[u][rem][p] = ans[u] + cnt[u] * (dep[u] - dep[p]);
  dp[u][rem][p] = calc(u, rem - 1, u);
  vector<int> a(rem + 1, 0);
  for (int i = 0; i < 10; i++) {
    int v = trie[u][i];
    if (v) {
      vector<int> tem(rem + 1, inf);
      for (int j = 0; j <= rem; j++) {
        for (int k = 0; j + k <= rem; k++) {
          tem[j + k] = min(tem[j + k], a[j] + calc(v, k, p));
        }
      }
      a = tem;
    }
  }
  return dp[u][rem][p] =
             min(dp[u][rem][p], cnt2[u] * (dep[u] - dep[p]) + a[rem]);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init();
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    int m;
    cin >> str >> m;
    insert(str, m);
  }
  memset(dp, 0x3f, sizeof(dp));
  cout << calc(0, k, 0) << endl;
}
